Cod sursa(job #2785494)

Utilizator casiannCasian casiann Data 18 octombrie 2021 19:38:43
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;

char subsir[11], sir[101];
int v_prefix[11], 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(){
    cin >> 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++; rez.push(i-p+1); p = v_prefix[p] + 1;}
        }else{
            p = v_prefix[subsir[p]];
        }
    }
    cout << cnt << '\n';
    while(!rez.empty()) {cout << rez.front() << " "; rez.pop();}
    return 0;
}