Cod sursa(job #3142107)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 19 iulie 2023 11:42:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int DIM = 2000010;
const int SOL_DIM = 1000;

char a[DIM], b[DIM], A[DIM], B[DIM];
int p[DIM];
int sol[SOL_DIM + 1], solCnt;

int main() {
    fin >> A >> B;
    strcpy(a + 1, A);
    strcpy(b + 1, B);
    int n = strlen(a + 1);
    int m = strlen(b + 1);

    p[1] = 0;
    int l = 0;
    for (int i = 2; i <= n; i++) {
        while (l != 0 && a[i] != a[l + 1])
            l = p[l];

        if (a[i] == a[l + 1])
            l++;
        p[i] = l;
    }

    l = 0;
    for (int i = 1; i <= m; i++) {
        while (l != 0 && b[i] != a[l + 1])
            l = p[l];

        if (b[i] == a[l + 1])
            l++;

        if (l == n) {
            solCnt++;
            if (solCnt <= 1000)
                sol[solCnt] = i - n + 1;
            l = p[l];
        }
    }

    fout << solCnt << '\n';
    for (int i = 1; i <= min(solCnt, SOL_DIM); i++)
        fout << sol[i] - 1 << ' ';

    return 0;
}