Cod sursa(job #2785563)

Utilizator casiannCasian casiann Data 18 octombrie 2021 21:57:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;

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

char subsir[2000005], sir[2000005];
int prefix_vector[2000005], rez[2000005];
int l_subsir, l_sir, cnt;

void construire_vector_prefix(char subsir[]){
    prefix_vector[0] = -1;
    prefix_vector[1] = 0 ;
    int nr_caractere_repetate = 0;
    for(int i=2; i<=l_subsir; i++){
        if(subsir[i] == subsir[nr_caractere_repetate + 1]){
            nr_caractere_repetate++;
        }else nr_caractere_repetate = 0;
        prefix_vector[i] = nr_caractere_repetate;
    }
}

int main(){
    fin >> subsir >> sir ;
    l_subsir = strlen(subsir), l_sir = strlen(sir);
    for(int i = l_subsir; i>=1; i--){
        subsir[i] = subsir[i-1];
    }
    for(int i = l_sir; i>=1; i--){
        sir[i] = sir[i-1];
    }
    construire_vector_prefix(subsir);
    int p = 0;
    for(int i=1; i<=l_sir; i++){
        while (p && subsir[p+1] != sir[i])
			p = prefix_vector[p];
		if (subsir[p+1] == sir[i])
			++p;
		if (p == l_subsir)
		{
			p = prefix_vector[p];
			++cnt;
			if (cnt <= 1000){
                rez[cnt] = i-l_subsir;
			}
        }
    }
    fout << cnt << '\n';
    if(cnt > 1000) cnt = 1000;
    for(int i=1; i<=cnt; i++){
        fout << rez[i] << ' ';
    }
    return 0;
}