Cod sursa(job #1947707)

Utilizator papinub2Papa Valentin papinub2 Data 31 martie 2017 11:00:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>

#define NMax 2000005

using namespace std;

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

int M, N, q, n, w;
char A[NMax], B[NMax];
int pi[NMax], pos[1024];

int main()
{
    in.get(A, NMax);

    in.get();

    in.get(B, NMax);

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

    for (int i = M; i >= 1; i--)
        A[i] = A[i-1];

    A[0] = ' ';

    for (int i = N; i >= 1; i--)
        B[i] = B[i-1];

    B[0] = ' ';

    for (int j = 2; pi[1] = 0, j <= M; j++)
    {
        while (w != 0 && A[w+1] != A[j])
            w = pi[w];

        if (A[w+1] == A[j])
            ++w;

        pi[j] = w;
    }

    for (int i = 1; i <= N; i++)
    {
        while (q != 0 && A[q+1] != B[i])
            q = pi[q];

        if (A[q+1] == B[i])
            q++;

        if (q == M)
        {
            q = pi[M];

            n++;

            if (n <= 1000)
                pos[n] = i - M;
        }
    }

    out << n << '\n';

    for (int i = 1; i <= min(n, 1000); i++)
        out << pos[i] << ' ';

    return 0;
}