Cod sursa(job #2720659)

Utilizator vansJos da pa perete vans Data 11 martie 2021 09:41:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e6;

int lps[NMAX + 1];
string pat, txt;
vector<int> ans;

void generLPS() {
    lps[0] = 0;
    for(int len = 0, i = 1; i < pat.length();)
        if(pat[len] == pat[i])
            lps[i] = len + 1,
            ++i, ++len;
        else {
            if(len != 0) len = lps[len - 1];
            else lps[len] = 0, ++i;
        }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    cin>>pat>>txt;
    generLPS();
    for(int i = 0, j = 0; i < txt.length() && ans.size() <= 1000;) {
        if(txt[i] == pat[j]) ++i, ++j;
        else {
            if(j == 0) ++i;
            else j = lps[j - 1];
        }
        if(j == pat.length()) ans.push_back(i - j);
    }
    printf("%d\n", (int)ans.size());
    for(const auto el : ans) printf("%d ", el);
    return 0;
}