Cod sursa(job #377659)

Utilizator yobunSasaujan Marian yobun Data 25 decembrie 2009 18:52:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>
#include<string.h>
#define NM 2000001

char s[NM],t[NM];

int ls,lt,u[NM],v[1001],nr;

 

void prefix()

{

int i,j;

u[0]=-1;

j=-1;

for(i=1;i<ls;i++)

{

while(j>-1&&s[i]!=s[j+1])j=u[j];

if(s[i]==s[j+1])j++;

u[i]=j;

}

}

int main()

{

freopen("strmatch.in","r",stdin);

freopen("strmatch.out","w",stdout);

scanf("%s%s",s,t);

ls=strlen(s);

lt=strlen(t);

int i,j;

prefix();

j=-1;

for(i=0;i<lt;i++)

{

while(j>-1&&t[i]!=s[j+1])j=u[j];

if(t[i]==s[j+1])j++;

if(j==ls-1)

{

nr++;

if(nr<=1000)v[nr]=i-ls+1;

}

}

printf("%d\n",nr);

if(nr>1000)nr=1000;

for(i=1;i<=nr;i++)printf("%d ",v[i]);

return 0;

}