Cod sursa(job #3237984)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 14 iulie 2024 19:02:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const string out[2]{ "No", "Yes" };
#define all(a) a.begin(), a.end()
#define var(a) #a
#define dbg(a) cerr << var(a) << " = " << a << nl
#define OK() cerr << "OK until line " << __LINE__ << nl
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

auto start_time = chrono::high_resolution_clock::now();

double getTime() {
    auto end_time = chrono::high_resolution_clock::now();
    return chrono::duration<double>(end_time - start_time).count();
}

template<typename T>
int rand(T a, T b) { return uniform_int_distribution<T>(a, b)(rng); }

template<typename T1, typename T2>
bool ckmax(T1& a, T2 b) { return a < b ? a = b, true : false; }

template<typename T1, typename T2>
bool ckmin(T1& a, T2 b) { return a > b ? a = b, true : false; }

const int nmax = 2e6;
int n, m;
string s, t;
int lps[nmax * 2 + 5];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> 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);
        }
    }
    fout << occ.size() << nl;
    if (occ.size() > 1000) {
        occ.resize(1000);
    }
    for (auto& x : occ) {
        fout << x << sp;
    }
}