Cod sursa(job #216604)

Utilizator Mishu91Andrei Misarca Mishu91 Data 24 octombrie 2008 23:15:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <cstring>

#define min(a, b) ((a < b)? a : b)
#define MAX_N 2000005
#define MAX_S 1005

int N, M, pi[MAX_N];
char A[MAX_N], B[MAX_N];
int Nr, P[MAX_S];

void kmp(char *S)
{
    int q = 0, i;
    for(i = 2; i <= N; ++i)
    {
        while(q && S[q] != S[i-1])
            q = pi[q];
        if(S[q] == S[i-1])
            ++q;
        pi[i] = q;
    }
}

int main()
{
    freopen("strmatch.in","rt",stdin);
    freopen("strmatch.out","wt",stdout);

    fgets(A, sizeof A, stdin);
    fgets(B, sizeof B, stdin);

    N = strlen(A) - 1;
    M = strlen(B) - 1;

    kmp(A);

    for(int i = 0, q = 0; i < M; ++i)
    {
        while(q && A[q] != B[i])
            q = pi[q];
        if(A[q] == B[i])
            ++q;
        if(q == N)
        {
            q = pi[N];
            ++Nr;
            if(Nr < 1001)
                P[Nr] = i - N + 1;
        }
    }

    printf("%d\n",Nr);
    for(int i = 1; i <= min(1000, Nr); ++i)
        printf("%d ",P[i]);
}