Cod sursa(job #3321075)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 8 noiembrie 2025 10:17:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

const int nmax = 2e6 + 5;
const string txt = "strmatch";
ifstream f(txt + ".in");
ofstream g(txt + ".out");

int lps[nmax];
string a, b;
vector<int> ans;

void prefsuf()
{
    int i = 2, lg = 0;
    while (i < a.size())
    {
        while (lg > 0 && a[lg + 1] != a[i]) lg = lps[lg];
        if (a[lg + 1] == a[i]) lg++;
        lps[i] = lg; i++;
    }
}

void KMP()
{
    int i = 1, lg = 0;
    while (i < b.size())
    {
        while (lg > 0 && a[lg + 1] != b[i]) lg = lps[lg];
        if (a[lg + 1] == b[i]) lg++;

        if (lg == a.size() - 1){
            ans.push_back(i - lg);
            lg = lps[lg];
        }
        i++;
    }
}

int main()
{
    f >> a >> b;

    string s1 = ' ' + a, s2 = ' ' + b;
    a = s1; b = s2;

    prefsuf(); KMP();

    g << ans.size() << '\n';
    for (int i = 0; i < min(1000, (int)ans.size()); i++)
        g << ans[i] << " ";
    return 0;
}