Cod sursa(job #3268698)

Utilizator Andercau_VasileAndercau Vasile Andercau_Vasile Data 16 ianuarie 2025 19:11:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define NMAX 2000005

char a[NMAX], b[NMAX];
int prefix[NMAX]; // lungimea celui mai lung prefix care este si sufix pentru pozitia i
int rez[NMAX];

void build(int n) {
    int k = 0; // lungimea celui mai lung prefix pana la pozitia precedenta
    for (int i = 2; i <= n; ++i) {
        while (k > 0 && a[k + 1] != a[i]) {
            k = prefix[k];
        }
        if (a[k + 1] == a[i]) {
            k++;
        }
        prefix[i] = k;
    }
}

int main() {
    fin.getline(a + 1, NMAX - 1);
    fin.getline(b + 1, NMAX - 1);
    a[0] = 'a';
    b[0] = 'b';

    int n = strlen(a + 1);
    int m = strlen(b + 1);

    build(n);

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

    fout << cnt << '\n';
    for (int i = 1; i <= cnt && i <= 1000; ++i) {
        fout << rez[i] << ' ';
    }
    return 0;
}