Cod sursa(job #2911081)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 26 iunie 2022 18:52:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda 3_iulie Marime 1.53 kb
#include <bits/stdc++.h>
using namespace std;
char a[2000001], b[2000001];
int pref[2000002];
int sol[2000002];
int main(void){
    ofstream cout("strmatch.out");
    ifstream cin("strmatch.in");
    cin >> a+1 >> b+1;

    int n,m, Lmax = 0, ans = 0;
    n = strlen(a+1);
    m = strlen(b+1);
    pref[1] = 0; /// primul prefix nu este si sufix
    for(int i = 2;i<=n;i++){
        /// cautam "sub sufixe" (sufixe care se afla in sufixul de lungime maxima si ne uitam daca il putem "mari"
        while(Lmax != 0 && a[i] != a[Lmax+1]){
            Lmax = pref[Lmax];
        }
        /// Daca putem creste sufixul vom incrementa Lungimea maxima
        if(a[Lmax+1] == a[i]){
            Lmax++;
        }
        /// actualizam lungimea maxima a sufixului de pe poz i
        pref[i] = Lmax;
    }
    Lmax = 0;
    for(int i = 1;i<=m;i++){
        while(Lmax != 0 && b[i] != a[Lmax+1]){
            Lmax = pref[Lmax];
        }
        if(b[i] == a[Lmax+1]){
            Lmax++;
        }
        /// vedem daca exista un sufix care este prefix din a cu lungimea lui a
        if(Lmax == n){
            ans++; /// crestem numarul de aparitii a lui A in B
            if(ans <= 1000)
                sol[ans] = i - n;
            Lmax = pref[Lmax]; /// ne uitam inca o data in "sub sufix"-ul  sufixului in care am gasit cuvantul pentru a vedea daca marind sufixul gasim un sufix de lungimea lui a
        }
    }
    cout << ans << endl;
    for(int i = 1;i<=min(ans, 1000);i++){
        cout << sol[i] << ' ';
    }
}