Cod sursa(job #2375778)

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

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)
        {
            sol.push_back(i - A.size() + 1);
            w = pi[w];
        }
    }

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