Cod sursa(job #2785566)

Utilizator casiannCasian casiann Data 18 octombrie 2021 22:02:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 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++){
        while (nr_caractere_repetate && subsir[nr_caractere_repetate+1] != subsir[i])
			nr_caractere_repetate = prefix_vector[nr_caractere_repetate];
		if (subsir[nr_caractere_repetate+1] == subsir[i])
			++nr_caractere_repetate;
		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;
}