Cod sursa(job #917603)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 10:06:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#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;
}