Cod sursa(job #3301932)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 1 iulie 2025 12:46:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector<int> compute_lps(const string &pattern)
{
    vector<int> lps(pattern.size(), 0);
    int k = 0;
    for(int i = 1; i < pattern.size(); i++)
    {
        while(k > 0 && pattern[i] != pattern[k])
            k = lps[k - 1];
        k += (pattern[i] == pattern[k]);
        lps[i] = k;
    }
    return lps;
}

vector<int> KMP(const string &text, const string &pattern)
{
    vector<int> lps = compute_lps(pattern), positions;
    int k = 0;
    for(int i = 0; i < text.size(); i++)
    {
        while(k > 0 && text[i] != pattern[k])
            k = lps[k - 1];
        k += (text[i] == pattern[k]);
        if(k == pattern.size())
        {
            positions.push_back(i - pattern.size() + 1);
            k = lps[k - 1];
        }
    }
    return positions;
}

int main()
{
    string A, B;
    fin >> A >> B;
    vector<int> ans = KMP(B, A);
    fout << ans.size() << "\n";
    for(int i = 0; i < min((int)ans.size(), 1000); i++)
        fout << ans[i] << " ";

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