Mai intai trebuie sa te autentifici.
Cod sursa(job #697614)
Utilizator | Data | 29 februarie 2012 10:13:04 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.79 kb |
#include <stdio.h>
#include <string.h>
#define NMax 2000005
int n,m;
char s1[NMax],s2[NMax];
int pi[NMax], pos[1024];
void make_prefix()
{
int i,q=0;
pi[0]=0;
for (i=1;i<=n;i++){
while ((q)&&(s1[q]!=s1[i])) q=pi[q-1];
if (s1[q]==s1[i]) q++;
pi[i]=q;
}
}
int main()
{
int i,q=0,nr=0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s",s1,s2); n=strlen(s1)-1; m=strlen(s2)-1;
make_prefix();
for (i=0;i<=m;i++)
{
while ((q)&&(s1[q]!=s2[i])) q=pi[q-1];
if (s1[q]==s2[i]) q++;
if (q==n+1){
q=pi[n];
nr++;
if (nr<=1000) pos[nr]=i-n;
}
}
printf("%d\n", nr);
if (nr>1000) nr=1000;
for (i=1;i<=nr;i++) printf("%d ",pos[i]);
printf("\n");
return 0;
}