Cod sursa(job #188977)

Utilizator Mishu91Andrei Misarca Mishu91 Data 11 mai 2008 11:47:20
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

#define MAX_N 2000001

string A1,A2;
int N1, N2;
int P[MAX_N], Sol[1002];

void read(void);
void make_prefix(void);
void kmp(void);

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

void read()
{
    char S[MAX_N];
    gets(S);
    A1 = string(S);
    N1 = A1.size();
    gets(S);
    A2 = string(S);
    N2 = A2.size();
}

void make_prefix()
{
    int i, q = -1;
    for(i = 1, P[1] = -1; i < N1; ++i)
    {
        while (q>=0 && A1[i] != A1[q+1])
            q = P[q];
        if(A1[i] == A1[q+1])
            ++q;
        P[i] = q;
    }
}

void kmp()
{
    int i, q = -1, n = 0;

    for(i = 0; i < N2; ++i)
    {
        while(q >=0  && A1[q + 1] != A2[i])
            q = P[q];
        if(A1[q + 1] == A2[i])
            ++q;
        if(q == N1 - 1)
        {
            q = P[N1 - 1];
            ++n;
            if(n < 1001)
                Sol[n] = i - N1 + 1;
        }
    }
    printf("%d\n", n);
    for (i = 1; i <= min(n, 1000); ++i)
        printf("%d ", Sol[i]);
}