Cod sursa(job #527853)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 1 februarie 2011 13:46:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
/// KMP

#include <stdio.h>
#include <string.h>

using namespace std;

const int nmax = 2000010;
char A[nmax], B[nmax], M, N;

void read()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);

    fgets(A,sizeof(A),stdin);
    fgets(B,sizeof(B),stdin);
    int i;
    M = strlen(B) - 1;
    N = strlen(A) - 1;
    for(i = N; i > 0; i--)
        A[i] = A[i - 1];
    for(i = M; i > 0; i--)
        B[i] = B[i - 1];
}

int pi[nmax], pos[1024];

void maquette()
{
    int i, q = 0;

    for(i = 2; i <= N; i++)
    {
        while(q && A[q + 1] != A[i])
            q = pi[q];
        if(A[q + 1] == A[i])
            q++;
        pi[i] = q;
    }
}

void solve()
{
    int i, q = 0, tot = 0;

    for(i = 1; i <= M; i++)
    {
        while(q && A[q + 1] != B[i])
            q = pi[q];
        if(A[q + 1] == B[i])
            q++;
        if(q == N)
        {
            tot++;
            q = pi[q];
            if(tot <= 1000)
                pos[tot] = i - N;
        }
    }
    printf("%d\n",tot);
    for(i = 1; i <= tot && i <= 1000; i++)
        printf("%d ",pos[i]);
    printf("\n");
}

int main()
{
    read();
    maquette();
    solve();
    return 0;
}