Cod sursa(job #2727552)

Utilizator vansJos da pa perete vans Data 22 martie 2021 08:35:55
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 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[st] = 0, ++dr;
}

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 = 0, j = 0; 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);
    }
    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;
}