Cod sursa(job #1325460)

Utilizator ccygnusMaygnus Pop ccygnus Data 23 ianuarie 2015 22:32:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<cstdio>
#define minim(a,b) ((a<b)?a:b)
int n,m;
char a[2000003],b[2000003];
int pi[2000003],pos[1024];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int i,q=0,N=0;
    gets(a);
    gets(b);
    for(;(a[m]>='A' && a[m]<='Z') || (a[m]>='a' && a[m]<='z') || (a[m]>='0' && a[m] <= '9');++m);
    for(;(b[n]>='A' && b[n]<='Z') || (b[n] >= 'a' && b[n] <= 'z') || (b[n]>='0' && b[n]<='9');++n);
    for(i=m;i;--i)
        a[i]=a[i-1];
    a[0]=' ';
    for(i=n;i;--i)
        b[i]=b[i-1];
    b[0]=' ';
    pi[1]=0;
    for(i=2;i<=m;++i)
        {
        while(q && a[q+1]!=a[i])
          q=pi[q];
        if (a[q+1]==a[i])
            ++q;
        pi[i]=q;
        }
    q=0;
    for(i=1;i<=n;++i)
        {
        while(q && a[q+1]!=b[i])
            q=pi[q];
        if (a[q+1]==b[i])
            ++q;
        if (q==m)
            {
            q=pi[m];
            ++N;
            if (N<=1000)
                pos[N]=i-m;
            }
        }
    printf("%d\n",N);
    for (i=1;i<=minim(N,1000);++i)
        printf("%d ", pos[i]);
    printf("\n");
return 0;
}