Cod sursa(job #517443)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 28 decembrie 2010 19:51:01
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 2000001
char *s1,*s2;
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);
s1=(char*)malloc(N*sizeof(char));
s2=(char*)malloc(N*sizeof(char));
scanf("%s\n",&s1);
scanf("%s\n",&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");}
free(s1);
free(s2);
fclose(stdin);
fclose(stdout);
return 0;}