Pagini recente » Cod sursa (job #2576537) | Cod sursa (job #3291700) | Cod sursa (job #3217099) | Cod sursa (job #2713484) | Cod sursa (job #2717742)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2e6;
int lpp[NMAX + 5], n, len;
string pat, str;
void precalc_lpp() {
pat = " " + pat + " "; str = " " + str;
lpp[1] = 0;
int k = 0; len = pat.length() - 2; n = str.length() - 1;
for(int i = 2; i <= len; i++) {
while(k > 0 && pat[k + 1] != pat[i])
k = lpp[k];
if(pat[k + 1] == pat[i]) k++;
lpp[i] = k;
}
}
int main()
{
fin >> pat >> str;
precalc_lpp();
//for(int i = 1; i <= len; i++) fout << lpp[i] << " "; fout << "\n";
int k = 0, res = 0;
vector <int> sol;
for(int i = 1; i <= n; i++) {
while(k > 0 && pat[k + 1] != str[i])
k = lpp[k];
if(pat[k + 1] == str[i]) k++;
if(k == len) {
if(res < 1000) sol.push_back(i - len + 1);
res++;
}
}
fout << res << "\n";
for(auto el : sol) fout << el - 1 << " ";
return 0;
}