Cod sursa(job #896035)

Utilizator paulbotabota paul paulbota Data 27 februarie 2013 13:35:41
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>

#define minim(a, b) ((a < b) ? a : b)
#define MAXN 2000005

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


void prefix()
{
    pi[1]=0;
    int k,i;
    for(i=2;i<=n;i++)
    {
        while(k>0 && a[k+1]!=a[i])
            k=pi[k];
        if(a[k+1]==a[i])
            k++;
        pi[i]=k;
    }
}

int kmp()
{
    int i,k=0,nr=0;
    for(i=1;i<=m;i++)
    {
        while(k>0 && a[k+1]!=b[i])
            k=pi[k];
        if(a[k+1]==b[i])
            k++;
        if(k==n)
        {
            k=pi[k];
            nr++;
            if(nr<=1000)
                pos[nr]=i-n;
        }
    }
    return nr;
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(a,sizeof(a),stdin);
    fgets(b,sizeof(b),stdin);
    for(;(a[n]>='A' && a[n]<='Z') || (a[n]>='a' && a[n]<='z') || (a[n]>='0' && a[n]<='9');n++);
    for(;(b[m]>='A' && b[m]<='Z') || (b[m]>='a' && b[m]<='z') || (b[m]>='0' && b[m]<='9');m++);
    int i;
    for(i=n;i;i--)
        a[i]=a[i-1];
    for(i=m;i;i--)
        b[i]=b[i-1];
    a[0]=' ';
    b[0]=' ';
    prefix();
    int nr=kmp();
    printf("%d\n",nr);
    for(i=1;i<=minim(nr,1000);i++)
        printf("%d ",pos[i]);
    printf("\n");
    return 0;
}