Cod sursa(job #1010563)

Utilizator laszloasandorLaszlo Sandor laszloasandor Data 15 octombrie 2013 10:41:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>

#define mini(a,b) ((a<b)?a:b)
#define NMax 2000005
#define fr(i,a,b) for(int i=a;i<=b;++i)

int n,m;
char a[NMax],b[NMax];
int pi[NMax],pos[1024];

void pref()
{
    int i, q = 0;

    for (i=2,pi[1]=0;i<=m;++i)
    {
        while(q&&a[q+1]!=a[i])
            q=pi[q];
        if(a[q+1]==a[i])
            ++q;
        pi[i]=q;
    }
}

int main()
{
    int i, q = 0, n1 = 0;

    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    fgets(a,sizeof(a),stdin);
    fgets(b,sizeof(b),stdin);

    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]=' ';

    pref();

    fr(i,1,n)
    {
        while(q&&a[q+1]!=b[i])
            q=pi[q];
        if (a[q+1]==b[i])
            ++q;
        if (q==m)
        {
            q=pi[m];
            ++n1;
            if (n1 <= 1000)
                pos[n1] = i-m;
        }
    }

    printf("%d\n",n1);
    fr(i,1,mini(n1,1000))
        printf("%d ",pos[i]);
    printf("\n");

    return 0;
}