Cod sursa(job #3291961)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 6 aprilie 2025 13:55:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX = 2000001;
int L[2 * NMAX];

void ZAlgo(string &s, int lgPattern)
{
    int counter = 0;
    vector<int> pos;
    L[0] = 1;
    int best = 0;
    for (int i = 1; i < s.size(); i++)
    {
        int rightBound = best + L[best];
        int j = L[best] - (rightBound - i);
        if (i < rightBound)
            L[i] = min(L[j], rightBound - i);
        while (i + L[i] < s.size() && s[L[i]] == s[i + L[i]])
        {
            L[i]++;
        }
        if (i + L[i] > rightBound)
        {
            best = i;
        }
        if (L[i] == lgPattern)
        {
            counter++;
            if (counter <= 1000)
            {
                pos.push_back(i - lgPattern - 1);
            }
        }
    }
    g << counter << '\n';
    for (auto p: pos)
    {
        g << p << ' ';
    }
}

int main()
{
    string A, B;
    f >> A >> B;
    /// A#B
    string finalString = A;
    finalString += "#";
    finalString += B;
    ZAlgo(finalString, A.size());
    return 0;
}