Pagini recente » Cod sursa (job #2851429) | Cod sursa (job #8437) | Cod sursa (job #2371587) | Cod sursa (job #681409) | Cod sursa (job #1299552)
//Z-algorithm
#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
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,cnt,p,aux;
fin.getline(s+1,4000005);
len=lena=strlen(s+1);
s[++len]='#';
fin.getline(s+len+1,4000005);
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)
{
cnt=0;
while ((i+cnt)<=len && s[cnt+1]==s[i+cnt]) cnt++;
z[i]=cnt;
lt=i;
rt=i+cnt-1;
}
else
{
p=i-lt+1;
aux=rt-i+1;
if (z[p]<aux) z[i]=z[p];
else
{
aux=rt+1;
while (aux<=len && s[aux]==s[aux-i+1]) aux++;
z[i]=aux-i;
lt=i;
rt=aux-i;
}
}
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;
}