Cod sursa(job #3359153)

Utilizator pkseVlad Bondoc pkse Data 25 iunie 2026 12:31:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 4'000'000;
int kmp[NMAX];
int ans[NMAX];
void makekmp(string &s) {
    for(int i = 1; i < s.size(); i ++) {
        int j = kmp[i - 1];
        while(j > 0 && s[i] != s[j]) {
            j = kmp[j - 1];
        }
        if(s[i] == s[j])
            j ++;
        kmp[i] = j;
    }
}

int main() {
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin.tie(0)->sync_with_stdio(0);
    
    string a, b; cin >> a >> b;
    string c = a + '#' + b;
    makekmp(c);
    int sz = 0;
    for(int i = a.size(); i < c.size(); i ++) {
        if(kmp[i] == a.size()) {
            ans[sz ++] = i - 2 * a.size();
        }
    }
    cout << sz << '\n';
    sz = min(sz, 1000);
    for(int i = 0; i < sz; i ++) {
        cout << ans[i] << ' ';
    }
}