Cod sursa(job #2222775)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 18 iulie 2018 00:44:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> P;
vector<int> answer;
string A, B;

int N, M;

void make_prefix()
{
    int k = 0;
    for (int i = 2; i <= N; ++i) {
        while (k && A[k + 1] != A[i])
            k = P[k];
        k += (A[k + 1] == A[i]);
        P[i] = k;
    }
}

int make_match()
{
    int total = 0;
    int k = 0;
    for (int i = 1; i <= M; ++i) {
        while (k && A[k + 1] != B[i])
            k = P[k];
        k += A[k + 1] == B[i];
        if (k == N) {
            ++ total;
            if(answer.size() < 1000)
                answer.emplace_back(i - N);
            k = P[k];
        }
    }
    return total;
}

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

    fin.sync_with_stdio(false);
    fin.tie(0);

    fin >> A >> B;
    N = A.size();
    M = B.size();
    P.resize(N + 1);

    A = "#" + A;
    B = "#" + B;

    make_prefix();
    fout << make_match() << "\n";
    for (auto it : answer)
        fout << it << " ";

    return 0;
}