Cod sursa(job #2727549)

Utilizator vansJos da pa perete vans Data 22 martie 2021 08:29:35
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e6;

int sl, bl, lps[NMAX + 3];
char small[NMAX + 3], big[NMAX + 3];
vector<int> ans;

void generLps() {
    lps[0] = 0;
    for(int st = 0, dr = 2; dr < sl;)
        if(small[st] == small[dr]) lps[dr++] = ++st;
        else if(st) st = lps[st - 1];
        else lps[dr++] = 0;
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s%s", small, big),
    sl = strlen(small), bl = strlen(big),
    generLps();
    for(int i = 1, j = 1; i < bl;) {
        if(big[i] == small[j]) ++i, ++j;
        else if(j) j = lps[j - 1];
        else ++i;
        if(j == sl) ans.push_back(i - j), j = lps[j - 1];
    }
    printf("%d\n", (int)ans.size());
    for(const auto el : ans) printf("%d ", el);
    return 0;
}