Pagini recente » Cod sursa (job #344039) | Cod sursa (job #1964957) | Cod sursa (job #1815008) | Cod sursa (job #487585) | Cod sursa (job #1300295)
//Z-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 s[XMAX];
int sol[NMAX],z[XMAX];
int main()
{
int i,lena,len,lt,rt,p,aux;
fin>>(s+1);
len=lena=strlen(s+1);
s[++len]='#';
fin>>(s+len+1);
i=len+1;
while (s[i]!=0) i++;
len=i-1;
z[1]=len;
lt=rt=0;
for (i=2;i<=len;i++)
if (i>rt)
{
lt=rt=i;
while (rt<=len && s[rt]==s[rt-i+1]) rt++;
rt--;
z[i]=rt-i+1;
}
else
{
p=i-lt+1;
if (z[p]<(rt-i+1)) z[i]=z[p];
else
{
aux=rt+1;
while (aux<=len && s[aux]==s[aux-i+1]) aux++;
aux--;
z[i]=aux-i+1;
lt=i;
rt=aux;
}
}
for (i=1;s[i]!='#';i++) ;
i++;
for (;i<=len;i++)
if (z[i]==lena) sol[++sol[0]]=i-lena-2;
fout<<sol[0]<<"\n";
for (i=1;i<=min(1000,sol[0]);i++) fout<<sol[i]<<" ";
fout<<"\n";
return 0;
}