Cod sursa(job #2375762)

Utilizator papinub2Papa Valentin papinub2 Data 8 martie 2019 11:59:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 2000005;

char A[Nmax], B[Nmax];

int main()
{
    int w = 0, A_size, B_size;

    in.get(A, Nmax);
    in.get();
    in.get(B, Nmax);

    A_size = strlen(A);
    B_size = strlen(B);

    vector<int> sol;
    vector<int> pi(A_size + 1);

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

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

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

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

        pi[i] = w;
    }

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

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

        if (w == A_size)
        {
            sol.push_back(i - A_size);
            w = pi[w];
        }
    }

    int Size = sol.size();
    out << Size << '\n';
    for (int i = 0; i < min(Size, 1000); i++)
        out << sol[i] << ' ';
    return 0;
}