Pagini recente » Cod sursa (job #1417204) | Cod sursa (job #2667407) | Cod sursa (job #369304) | Cod sursa (job #841410) | Cod sursa (job #1812127)
///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[20000000],sol[100000],nr=0,n,m;
void compute_Z() {
n=concat.length();
int L=-1,R=-1;
for(int i=1;i<n;i++)
{
if(i>R)
{ if(concat[0]==concat[i])
{L=i;
R=i-1;
for(int j = 0, k = i; k < n && concat[j] == concat[k]; j++, k++) Z[i] ++,R ++;
}
else Z[i] = 0;
}
else
{int before = i - L;
if(Z[before] < R - i + 1) Z[i]=Z[before];
else {Z[i]=R-i+1;
L = i;
for(int before = Z[i]; R + 1 <n && concat[R + 1] == concat[before]; before++, R++) Z[i] ++;
}
}
}
}
int main()
{ f>>pattern>>text;
m=pattern.length();
concat=pattern+text;
compute_Z();
for(int i =m;i<n;i++) if(Z[i]>=m) if(nr<1000) sol[++nr]=i-m;
g<<nr<<'\n';
for(int i=1;i<=nr;i++) g<<sol[i]<<' ';
}