Cod sursa(job #946175)

Utilizator Ionut228Ionut Calofir Ionut228 Data 3 mai 2013 23:22:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[2000002], B[2000002];
int pi[2000002], v[1002];
int N, M, a;

void prefix()
{
    int k = 0;
    pi[1] = 0;
    for (int i = 2; i <= N; ++i)
    {
        while (k > 0 && A[k + 1] != A[i])
            k = pi[k];
        if (A[k + 1] == A[i])
            ++k;
        pi[i] = k;
    }
}

void KMP()
{
    int q = 0;
    for (int i = 1; i <= M; ++i)
    {
        while (q > 0 && A[q + 1] != B[i])
            q = pi[q];
        if (A[q + 1] == B[i])
            ++q;
        if (q == N)
        {
            q = pi[N];
            ++a;
            if (a <= 1000)
                v[a] = i - N;
        }
    }
}

void afisare()
{
    fout << a << '\n';
    for (int i = 1; i <= a; ++i)
        fout << v[i] << " ";
}

int main()
{
    fin.getline(A, 2000002);
    fin.getline(B, 2000002);

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

    for (int i = N; i >= 1; --i)
        A[i] = A[i - 1];
    A[0] = ' ';
    A[N + 1] = ' ';
    for (int i = M; i >= 1; --i)
        B[i] = B[i - 1];
    B[0] = ' ';
    B[M + 1] = ' ';

    prefix();
    KMP();

    afisare();

    fin.close();
    fout.close();
}