Cod sursa(job #2720670)

Utilizator vansJos da pa perete vans Data 11 martie 2021 09:54:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 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();) {
        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);
    }
    int n = min(1000, (int)ans.size());
    printf("%d\n", (int)ans.size());
    for(int i = 0; i < n; ++i) printf("%d ", ans[i]);
    return 0;
}