Cod sursa(job #1004895)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 3 octombrie 2013 19:41:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
#include<string.h>
char a[2000005],b[2000005];
unsigned a2[2000005],s[1005];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    unsigned n,m,i,j,x,l=0;
gets(a+1);
gets(b+1);
n=strlen(a+1);
m=strlen(b+1);
a2[1]=0;
for(i=2;i<=n;i++)
{
    j=a2[i-1];
    while(a[j+1]!=a[i] && j>1)
        {
j=a2[j];
        }
        if(a[j+1]==a[i])
        a2[i]=j+1;
}
a[m+1]='1';
a[n+1]='2';
j=0;
for(i=1;i<=m;i++)
{
while(b[i]!=a[j+1] && j>0)
{
    j=a2[j];
}
if(a[j+1]==b[i])
j++;
if(j==n)
{
    l++;
    s[l]=i-n;
    if(l==1000)
        break;
}
}
printf("%u\n",l);
for(i=1;i<=l;i++)
    printf("%u ",s[i]);
    return 0;
}