Mai intai trebuie sa te autentifici.
Cod sursa(job #517440)
Utilizator | Data | 28 decembrie 2010 19:46:30 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 18 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.94 kb |
#include<stdio.h>
#include<string.h>
#define N 2000001
char s1[N],s2[N];
long v[N],p[N],n,m;
int main()
{long i,k=0,t=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s1);
gets(s2);
m=strlen(s1);
n=strlen(s2);
p[1]=0;
if(m>=n)
{for(i=1;i<m;i++)
{while(k>0&&s2[k+1]!=s1[i])
k=p[k];
if(s2[k+1]==s1[i])
k++;
if(k==n-1)
v[t++]=i-n+1;}}
else
{for(i=1;i<n;i++)
{while(k>0&&s1[k+1]!=s2[i])
k=p[k];
if(s1[k+1]==s2[i])
k++;
if(k==m-1)
v[t++]=i-m+1;}}
printf("%ld\n",t);
if(t<=1000)
{for(i=0;i<t;i++)
printf("%ld ",v[i]);
printf("\n");}
else
{for(i=0;i<1000;i++)
printf("%ld ",v[i]);
printf("\n");}
fclose(stdin);
fclose(stdout);
return 0;}