Cod sursa(job #1386637)

Utilizator raztaapDumitru raztaap Data 13 martie 2015 09:44:31
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <cstring>
#define LGMAX 2000100
#define min(a,b) a<b?a:b
char N[LGMAX], M[LGMAX];
int pi[LGMAX], pos[1024], n, m,nr;
void citire()
{
    gets(N);
    gets(M);
}
void make_prefix()
{
    n=strlen(N);
    int k=0,i;
    pi[0]=0;
    for(i=1;i<n;++i)
    {
        while(k&&N[k+1]!=N[i])
            k=pi[k];
        if(N[k+1]==N[i])
            ++k;
        pi[i]=k;
    }
}
void KMP()
{
    nr=0;
    make_prefix();
    m=strlen(M);
    n=strlen(N);
    int q=0,i;
    for(i=0;i<m;++i)
    {
        while(q&&N[q+1]!=M[i])
            q=pi[q];
        if(N[q+1]==M[i])
            ++q;
        if(q==n-1)
        {
            q = pi[n-1];
            ++nr;
            if (nr <= 1000)
                pos[nr] = i;
        }
    }
}
void afisare()
{
    int i;
    printf("%d\n", nr);
    for(i=1;i<=(min(nr,1000));++i)
        printf("%d ", pos[i]);
}
void rezolva_problema()
{
    citire();
    KMP();
    afisare();
}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    rezolva_problema();
    return 0;
}