Cod sursa(job #1378860)

Utilizator valexVochescu Alexandru valex Data 6 martie 2015 14:50:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <cstring>
using namespace std;

#define lmax 2000002

char x[lmax],y[lmax];
int pi[lmax],di[lmax];

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

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

    fgets(x+1, lmax, stdin);
    fgets(y+1, lmax, stdin);

    x[0] = ' '; y[0] = ' ';
    x[strlen(x)-1] = y[strlen(y)-1] = 0;

    prefix();
    int i,k,m=strlen(y)-1,n=strlen(x)-1,nr=0;
    k=0;
    for (i=1;i<=m;i++)
    {
        while (k>0 && y[i]!=x[k+1])
            k=pi[k];
        if (y[i]==x[k+1]) k++;
        di[i]=k;
        if (di[i]==n) nr++;
    }
    printf("%d\n",nr);
    for (i=1;i<=m;i++)
        if (di[i]==n) printf("%d ",i-n);
    return 0;
}