Pagini recente » Borderou de evaluare (job #447725) | Borderou de evaluare (job #2968503) | Borderou de evaluare (job #383823) | Borderou de evaluare (job #62220) | Cod sursa (job #916309)
Cod sursa(job #916309)
#include<cstdio>
#include<cstring>
int n,m,i,k,nr,v[2000005],w[2000005];
char s[2000005],t[2000005];
void citire()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s+1);
gets(t+1);
n=strlen(s+1);
m=strlen(t+1);
}
void prefix()
{
k=0;
for(i=2;i<=n;i++){
while(k>0 && s[k+1]!=s[i])k=v[k];
if(s[k+1]==s[i])k++;
v[i]=k;
}
}
void kmp()
{
k=0;
for(i=1;i<=m;i++){
while(k>0 && s[k+1]!=t[i])k=v[k];
if(s[k+1]==t[i])k++;
if(k==n){
nr++;
w[nr]=i-n;
k=v[k];
}
}
}
void afisare()
{
printf("%d\n",nr);
if(nr>1000)nr=1000;
for(i=1;i<=nr;i++)printf("%d ",w[i]);
}
int main()
{
citire();
prefix();
kmp();
afisare();
return 0;
}