Cod sursa(job #1378901)

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

#define lmax 2000002
#define minim(a, b) ((a < b) ? a : b)

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

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++;
            if (nr<=1000) sol[nr]=i-n;
        }
    }
    printf("%d\n",nr);
    for (i=1;i<=minim(nr,1000);i++)
        printf("%d ",sol[i]);
    return 0;
}