Cod sursa(job #2909833)

Utilizator maiaauUngureanu Maia maiaau Data 16 iunie 2022 09:43:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;

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

const int N = 2e6;

char A[N + 5], B[N + 5];
int p[N + 5], t;
set<int> solutii;

int main()
{
    f >> A + 1 >> B + 1;
    int n = strlen(A + 1), m = strlen(B + 1);

    int q = 0;
    for (int i = 2; i <= n; i++){
        while (q > 0 && A[i] != A[q + 1]) q = p[q];
        if (A[i] == A[q + 1])q++;
        p[i] = q;
    }

    //for (int i = 1; i <= n; i++) cout << p[i] << ' ';

    q = 0;
    for (int i = 1; i <= m; i++)
    {
        while (q > 0 && A[q + 1] != B[i]) q = p[q];
        if (B[i] == A[q + 1]) q++;
        if (q == n){
            t++;
            solutii.insert(i - n);
            if(t == 1001) break;
        }
    }

    g << t<< '\n';
    for (auto i: solutii) g << i << ' ';
    return 0;
}