Cod sursa(job #2974840)

Utilizator IanisBelu Ianis Ianis Data 4 februarie 2023 18:44:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#include <bits/stdc++.h>
#define endl '\n'
#endif

const int NMAX = 2e6+5;

int n, m;
char a[NMAX], b[NMAX];
int lps[NMAX];
vector<int> ans;

void read() {
    fin >> b >> a;
    n = strlen(a);
    m = strlen(b);
}

void precalc() {
    int j = 0;
    for (int i = 1; i < m; i++) {
        if (b[i] == b[j]) {
            lps[i] = ++j;
        } else {
            if (j == 0) {
                lps[i] = 0;
            } else {
                j = lps[j - 1];
                i--;
            }
        }
    }
}

void solve() {
    for (int i = 0, j = 0; i < n; i++) {
        if (a[i] == b[j]) {
            j++;
            if (j == m) {
                j = lps[j - 1];
                ans.push_back(i - m + 1);
            }    
        } else {
            if (j == 0) continue;
            j = lps[j - 1];
            i--;
        }
    }
    fout << ans.size() << endl;
    for (auto &it : ans)
        fout << it << ' ';
}

int main() {
    read();
    precalc();
    solve();
    return 0;
}