Cod sursa(job #1204207)

Utilizator Pintilie_AndreiFII-Pintilie Andrei Pintilie_Andrei Data 2 iulie 2014 12:44:32
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <cstring>
#define N 2000010
using namespace std;

char a[N],b[N];
int n,m,pi[N];
int soln,sol[1010];

void R()
{
    freopen("strmatch.in","r",stdin);
    scanf("%s %s",(a+1),(b+1) );
    n=strlen(a+1);
    m=strlen(b+1);
}

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

    }
}

void KMP()
{
    int i,ind=0;
    for(i=1; i<=m; i++)
    {
        while(ind>0 && a[ind+1]!=b[i])
            ind=pi[ind];
        if(a[ind+1]=b[i])
            ind++;
        if(ind==n)
        {
            ind=pi[ind];
            soln++;
            if(soln<=1000)
            sol[soln]=i-n;

        }
    }


}

int main()
{
    R();
    Prefix();
    KMP();
    freopen("strmach.out","w",stdout);
    printf("%d\n",soln);
    if(soln>1000) soln=1000;
    for(int i=1; i<=soln; i++ )
        printf("%d ",sol[i]);
    return 0;
}