Pagini recente » Cod sursa (job #1065981) | Cod sursa (job #161440) | Cod sursa (job #88949) | Cod sursa (job #1299566) | Cod sursa (job #1299564)
//Z-algorithm
#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
using namespace std;
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;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin.sync_with_stdio(false);
cin>>(s+1);
len=lena=strlen(s+1);
s[++len]='#';
cin>>(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)
{
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;
cout<<sol[0]<<"\n";
for (i=1;i<=min(1000,sol[0]);i++) cout<<sol[i]<<" ";
cout<<"\n";
return 0;
}