Cod sursa(job #3301761)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 29 iunie 2025 18:20:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;

vector<int> prefix_function(const string &P)
{
    vector<int> prefix(P.size());
    prefix[0] = 0;
    int k = 0;
    for(int i = 1; i < P.size(); i++)
    {
        while(k > 0 && P[k] != P[i])
            k = prefix[k - 1];
        k += (P[k] == P[i]);
        prefix[i] = k;
    }
    return prefix;
}

int main()
{
    fin >> A >> B;
    string S = A + '*' + B;
    vector<int> prefix = prefix_function(S), positions;
    for(int i = A.size() + 1; i < S.size() && positions.size() <= 1000; i++)
        if(prefix[i] == A.size())
            positions.push_back(i - 2 * A.size());
    fout << positions.size() << "\n";
    for(int poz : positions)
        fout << poz << " ";

    fin.close();
    fout.close();
    return 0;
}