Cod sursa(job #2649804)

Utilizator antanaAntonia Boca antana Data 16 septembrie 2020 14:57:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 1e6;

vector <int> ans;

int pi[NMAX * 2 + 1];
char a[NMAX * 2 + 2], b[NMAX * 2 + 1];

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    int n, m, nr = 0;
    scanf("%s\n", (a + 1));
    n = strlen(a + 1);
    a[++n] = '#';
    scanf("%s", (b + 1));
    m = strlen(b + 1);

    //compute pi
    pi[1] = 0;
    int k = 0;
    for (int i = 2; i <= n; i++) {
        while (k!= 0 && a[ i ] != a[k + 1]) {
            k = pi[k];
        }
        if (a[ i ] == a[k + 1]) {
            k++;
        }
        pi[ i ] = k;
    }

    k = 0;
    for (int i = 1; i <= m; i++) {
        while (k != 0 && b[ i ] != a[k + 1]) {
            k = pi[ k ];
        }
        if (b[ i ] == a[k + 1]) {
            k++;
        }
        if (k == n-1) {
            nr++;
            if (ans.size() < 1000) {
                ans.push_back(i - n + 1);
            }
        }
    }

    cout << nr << '\n';
    for (auto idx: ans) {
        cout << idx << " ";
    }

}