Cod sursa(job #2922169)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 5 septembrie 2022 15:57:54
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 2e6;

int prec[NMAX + 5];

void CalcPrec(string &s) {
    int n = s.length();

    int j = 0;
    for(int i = 1; i < n; i++) {
        while(j && s[i] != s[j])
            j = prec[j - 1];

        if(s[i] == s[j])
            j++;

        prec[i] = j;
    }
}

int main()
{
    string a, b;

    cin >> a >> b;

    int n, m;

    n = a.length();
    m = b.length();

    CalcPrec(a);

    vector<int> ans;

    int i = 0;
    for(int j = 0; j < m; j++) {
        if(i && a[i] != b[j])
            i = prec[i - 1];

        if(a[i] == b[j]) {
            i++;

            if(i == n) {
                ans.emplace_back(j - n);
                i = prec[i - 1];
            }
        }
    }

    cout << ans.size() << '\n';

    for(auto x : ans)
        cout << x + 1 << " ";

    return 0;
}