Pagini recente » Cod sursa (job #2664127) | Cod sursa (job #2504916) | Cod sursa (job #2865775) | Cod sursa (job #258685) | Cod sursa (job #2460505)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define NMAX 2000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int phi[2*NMAX+10];
string s, s1, s2;
vector <int> sol;
int main()
{
f >> s1 >> s2;
s = s1 + '#' + s2;
int i=1, j=0;
while(i < s.size())
{ if(s[i] == s[j])
{ j++;
phi[i] = j;
i++;
}
else
{ if(j) j = phi[j-1];
else i++;
}
}
for(int i=0; i<s.size(); i++) if(phi[i] == s1.size()) sol.push_back(i-2*s1.size());
g << sol.size() << '\n';
int l = sol.size();
l = min(1000, l);
for(int i=0; i<l; i++) g << sol[i] << ' ';
g << '\n';
return 0;
}