Cod sursa(job #3204955)

Utilizator ggaaggaabbiigoteciuc gabriel ggaaggaabbii Data 18 februarie 2024 13:32:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

#define MAXN 2000010

char a[MAXN], b[MAXN];
int n, m, p[MAXN];

void build() {
    int k = 0;
    for (int i = 2; i <= n; ++i) {
        while (k > 0 && a[i] != a[k + 1]) {
            k = p[k];
        }
        if (a[i] == a[k + 1]) {
            ++k;
        }
        p[i] = k;
    }
}
int nr;
int v[MAXN];
int main()
{
    f.getline(a + 1, MAXN - 1);
    f.getline(b + 1, MAXN - 1);
    a[0] = 'a';
    b[0] = 'b';
    n = strlen(a) - 1;
    m = strlen(b) - 1;
    build();

    int k = 0;

    for (int i = 1; i <= m; ++i) {
        while (k > 0 && a[k + 1] != b[i]) {
            k = p[k];
        }
        if (a[k + 1] == b[i]) {
            ++k;
        }
        if (k == n) {
            ++nr;
            if (nr <= 1000) {
                v[nr] = i - k;
            }
            k = p[k];
        }
    }

    g << nr << '\n';
    for (int i = 1; i <= nr && i <= 1000; ++i) {
        g << v[i] << ' ';
    }

    return 0;
}