Cod sursa(job #2785512)

Utilizator casiannCasian casiann Data 18 octombrie 2021 19:58:11
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;

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

char subsir[2000001], sir[2000001];
int v_prefix[2000001], cnt;
queue <int> rez;

void construire_vector_prefix(char subsir[]){
    v_prefix[0] = 0;
    int prefix = 0;
    for(int i=1; i<strlen(subsir); i++){
        if(subsir[i] == subsir[prefix]){
            v_prefix[i] = v_prefix[i-1] + 1;
            prefix++;
        }else{
            v_prefix[i] = 0;
            prefix = 0;
        }
    }
}

int main(){
    fin >> subsir >> sir;
    construire_vector_prefix(subsir);
    int p = 0;
    for(int i=0; i<strlen(sir); i++){
        if(sir[i] == subsir[p]){
            p++;
            if(p == strlen(subsir) && cnt < 1000) {cnt++; rez.push(i-p+1); p = v_prefix[p] + 1;}
        }else {
            p = v_prefix[p];
        }
    }
    fout << cnt << '\n';
    while(!rez.empty()) {fout << rez.front() << " "; rez.pop();}
    return 0;
}