Cod sursa(job #2375695)

Utilizator papinub2Papa Valentin papinub2 Data 8 martie 2019 11:35:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>

using namespace std;

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

int main()
{
    int w = -1;
    string A, B;
    in >> A >> B;

    vector<int> sol;
    vector<int> pi(A.size() + 1);

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

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

        pi[i] = w;
    }

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

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

        if (w == A.size() - 1)
        {
            if (sol.size() < 1000)
                sol.push_back(i - A.size() + 1);
            w = pi[w];
        }
    }

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