Cod sursa(job #3240579)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 17 august 2024 16:50:06
Problema Potrivirea sirurilor Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)(x.size())
#define pii pair<int, int>
#define fs first
#define sd second
const int N = 150, V = 25, INF = 1e9, mod = 19997;

int n, m, lps[N];
string s, t;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    cin >> s >> t;
    n = s.size();
    m = t.size();
    s = '#' + s;
    t = '#' + t;
    s += t;
    int len = n + m + 1;
    for (int i = 2; i <= len; i++) {
        int j = lps[i - 1];
        while (j > 0 && s[j + 1] != s[i]) {
            j = lps[j];
        }
        if (s[j + 1] == s[i]) {
            j++;
        }
        lps[i] = j;
    }
    vector<int> occ;
    for (int i = n + 2; i <= len; i++) {
        if (lps[i] == n) {
            occ.push_back(i - 2 * n - 1);
        }
    }
    cout << occ.size() << '\n';
    if (occ.size() > 1000)
        occ.resize(1000);
    for (auto x : occ) {
        cout << x << ' ';
    }
}