Cod sursa(job #3321089)

Utilizator Ics.maker09Iancu Cezar-Stefan Ics.maker09 Data 8 noiembrie 2025 10:27:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, ans;
string a, b;
int lps[2000005], sol[2000005];
void initLPS() {
    int i = 1, lg = 0;
    while (i < n) {
        if (a[i] == a[lg]) {
            lg++;
            lps[i++] = lg;
        } else {
            if (lg) lg = lps[lg - 1];
            else lps[i++] = 0;
        }
    }
}

void kmpSearch() {
    int i = 0, lg = 0;
    while (i < m) {
        if (b[i] == a[lg]) {
            i++;
            lg++;
            if (lg == n) {
                sol[++ans] = i - lg;
                lg = lps[lg - 1];
            }
        } else {
            if (lg) lg = lps[lg - 1];
            else i++;
        }
    }
    g << ans << '\n';
    for (int i=1;i<=min(ans, 1000);i++) g<<sol[i]<<" ";
}

int main() {
    f >>a;
    f.get();
    f >>b;
    n=a.size();
    m=b.size();
    initLPS();
    kmpSearch();
    return 0;
}