Pagini recente » Cod sursa (job #227255) | Cod sursa (job #2184312) | Cod sursa (job #3152990) | Cod sursa (job #2967413) | Cod sursa (job #1288177)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[4000005],s2[2000005];
int z[4000005],l,r,kp,a,nsol,sol[2000005];
int main()
{ int i,len,cuvlen;
f.get(s+1,2000003); f.get();
f.get(s2,2000003);
cuvlen=strlen(s+1);
strcat(s+1,s2);
len=strlen(s+1);
l=0; r=0;
for(i=2;i<=len;i++)
{
if (i>r)
{
while(s[z[i]+1]==s[i+z[i]])
z[i]++;
l=i; r=l+z[i]-1;
}
else
{
kp=i-l+1; a=r-l+1;
if (kp+z[kp]-1<a) z[i]=z[kp];
else
{
z[i]=a-kp+1;
while(s[z[i]+1]==s[i+z[i]])
z[i]++;
}
}
if (i>cuvlen && z[i]>=cuvlen) {nsol++; sol[nsol]=i-cuvlen-1;}
}
g<<nsol<<"\n";
for(i=1;i<=nsol;i++)
g<<sol[i]<<" ";
return 0;
}