Pagini recente » Cod sursa (job #2921284) | Cod sursa (job #1560719) | Cod sursa (job #1438271) | Cod sursa (job #3290584) | Cod sursa (job #2460906)
#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], nr;
string s, s1, s2;
vector <int> sol;
int main()
{
f >> s1 >> s2;
s = s1 + '*' + s2;
phi[0] = -1;
for(int i=1; i<s.size(); i++)
{ int x = i - 1;
while(s[phi[x]+1] != s[i] && phi[x] != -1) x = phi[x];
if(s[phi[x]+1] == s[i]) phi[i] = phi[x] + 1;
else phi[i] = -1;
}
int n = s1.size();
for(int i=n; i<s.size(); i++)
if(phi[i] == n-1)
{ nr++;
if(nr <= 1000) sol.push_back(i-2*n);
}
g << nr << '\n';
for(int i=0; i<sol.size(); i++) g << sol[i] << ' ';
g << '\n';
return 0;
}