Mai intai trebuie sa te autentifici.
Cod sursa(job #169920)
Utilizator | Data | 2 aprilie 2008 11:03:42 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.69 kb |
#include<stdio.h>
#include<string.h>
int main () {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
char a[2000000],b[2000000];
int m,n,i,k=0,pi[2000000],v[1000],q=0;
fgets(a+1,200000,stdin);
fgets(b+1,200000,stdin);
n=strlen(a+1);
m=strlen(b+1);
--n;--m;
pi[0]=0;
pi[1]=0;
for(i=2;i<=n;++i){
while((k>0)&&(a[k+1]!=a[i]))
k=pi[k];
if(a[k+1]==a[i])
++k;
pi[i]=k;
}
k=0;
for(i=1;i<=m;++i){
while((k>0)&&(a[k+1]!=b[i]))
k=pi[k];
if(a[k+1]==b[i])
++k;
if(k==n){
if(q<1000)
v[q]=i-n;
++q;
}
}
printf("%d\n",q);
if(q){
for(i=0;i<q&&i<999;++i)
printf("%d ",v[i]);
printf("\n");
}
return 0;
}