Cod sursa(job #2732413)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 28 martie 2021 22:39:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

const int SOLMAX = 1000;
const int LMAX = 2000000;

string A;
string B;

int dp[1 + 2 * LMAX + 1];

vector<int> sol;

int sizeA;

void precalcPrefix()
{
    dp[1] = 0;
    int pi = 0;

    for (int i = 2; i < A.size(); i++)
    {
        while (pi > 0 && A[i] != A[pi + 1])
        {
            pi = dp[pi];
        }

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

        dp[i] = pi;

        if (dp[i] == sizeA)
        {
            sol.emplace_back(i - sizeA - sizeA + 1 - 2);
        }
    }
}

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

    in >> A >> B;

    sizeA = A.size();

    A = ' ' + A + '$' + B;

    precalcPrefix();

    out << sol.size() << '\n';

    for (int i = 0; i < min((int)sol.size(), SOLMAX); i++)
    {
        out << sol[i] << ' ';
    }

    return 0;
}