Cod sursa(job #3226851)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 23 aprilie 2024 07:20:43
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int Nmax = 2000005;

string a, b;
int lps[Nmax];
int times_found;
vector<int> sol;

void citire(){
    fin >> a >> b;
}

void init_lps(string pattern){
    int len;

    lps[0] = 0;
    len = 0;

    for(unsigned i = 1; i < a.size(); i++){
        while(len > 0 && pattern[len] != pattern[i]){
            len = lps[len - 1];
        }

        len++;
        lps[i] = len;
    }
}

void kmp(string a, string b){
    unsigned indice_a, indice_b;

    init_lps(a);

    times_found = 0;

    indice_a = 0;
    indice_b = 0;
    while((b.size() - indice_b) > (a.size() - indice_a)){
        if(b[indice_b] == a[indice_a]){
            indice_a++;
            indice_b++;
        }

        if(indice_a == a.size()){
            times_found++;

            if(times_found <= 1000){
                sol.push_back(indice_b - indice_a);
            }

            indice_a = lps[indice_a - 1];
        }
        else if(indice_b < b.size() && a[indice_a] != b[indice_b]){
            if(indice_a != 0){
                indice_a = lps[indice_a - 1];
            }
            else{
                indice_b++;
            }
        }
    }
}

void afisare(){
    fout << times_found << '\n';
    for(int i = 0; i < min(times_found, 1000); i++){
        fout << sol[i] << " ";
    }
}

int main(){
    citire();

    kmp(a, b);
    afisare();

    return 0;
}