Pagini recente » Cod sursa (job #975917) | Cod sursa (job #1159678) | Cod sursa (job #57990) | Cod sursa (job #571425) | Cod sursa (job #1812141)
///Z-Algorithm
///radu.leonardo
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pattern,text,concat;
int Z[4000000],sol[1001],nr=0,n,m;
void compute_Z()
{ n=concat.size();
int L=0,R=0, k;
for (int i=1;i<n;++i)
{
if (i>R)
{ L=R=i;
while(R<n&&concat[R-L]==concat[R])R++;
Z[i]=R-L;R--;
}
else
{ k=i-L;
if (Z[k]<R-i+1) Z[i]=Z[k];
else
{ L=i;
while(R<n&&concat[R-L]==concat[R])R++;
Z[i]=R-L;R--;
}
}
}
}
int main()
{ f>>pattern>>text;
concat = pattern + text;
compute_Z();
m=pattern.size();
for (int i = 0; i < n; ++i) {if (Z[i] == m) sol[++nr]=i-m;if(nr==1000) break;}
g<<nr<<'\n';
for(int i=1;i<=nr;i++) g<<sol[i]<<' ';
}