Pagini recente » Cod sursa (job #840959) | Cod sursa (job #2655863) | Cod sursa (job #1569862) | Cod sursa (job #1979424) | Cod sursa (job #1299513)
//K-algorithm
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2000005;
const int XMAX=4000005;
char a[NMAX],b[NMAX],c[XMAX];
int sol[NMAX],pi[XMAX];
int main()
{
int i,lena,lenb,lenc,dr;
fin>>(a+1);
lena=strlen(a+1);
fin>>(b+1);
lenb=strlen(b+1);
for (i=1;i<=lena;i++) c[i]=a[i];
c[lena+1]='#';
for (i=1;i<=lenb;i++) c[lena+1+i]=b[i];
lenc=lena+lenb+1;
pi[1]=0;
for (i=2;i<=lenc;i++)
{
dr=pi[i-1];
while (dr && c[dr+1]!=c[i]) dr=pi[dr];
if (c[dr+1]==c[i]) dr++;
pi[i]=dr;
if (pi[i]==lena) sol[++sol[0]]=i-lena+1;
}
fout<<sol[0]<<"\n";
for (i=1;i<=min(1000,sol[0]);i++)
{
sol[i]-=lena;
sol[i]-=2;
fout<<sol[i]<<" ";
}
fout<<"\n";
return 0;
}