Cod sursa(job #2754995)

Utilizator Mirc100Mircea Octavian Mirc100 Data 26 mai 2021 18:50:10
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>
#define N 2000002
#define NR_POZ 1000
using namespace std;
int nr;
int poz[NR_POZ];
int pi[N]; 
char s[N],t[N];

void rabin_karp(char *s, char *t) {
    int p = 31; 
    int m = 1e9 + 9;
    int ns = strlen(s), nt = strlen(t);

    vector<long long> p_pow(max(ns, nt)); 
    p_pow[0] = 1; 
    for (int i = 1; i <  p_pow.size(); i++) {
	
        p_pow[i] = (p_pow[i-1] * p) % m;
         
    }

    vector<int> hash_t(nt + 1, 0); 
    for (int i = 0; i < nt; i++)
    	if(t[i]<='Z')
        	hash_t[i+1] = (hash_t[i] + (t[i] - 'A' + 1) * p_pow[i]) % m; 
        else
        	hash_t[i+1] = (hash_t[i] + (t[i] - 'a' + 1) * p_pow[i]) % m; 
    int hash_s = 0; 
    for (int i = 0; i < ns; i++) {
	        if(s[i]<='Z')
				hash_s = (hash_s + (s[i] - 'A' + 1) * p_pow[i]) % m; 
			else
				hash_s = (hash_s + (s[i] - 'a' + 1) * p_pow[i]) % m; 
			 
	}
    for (int i = 0; i + ns - 1 < nt; i++) { 
    	
        int cur_h = (hash_t[i+ns] + m - hash_t[i]) % m; 
         
        if (cur_h == hash_s * p_pow[i] % m){
        	
		    poz[nr]=i;
            nr++;
        }
    }

}

int main(){
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");

	f>>s>>t;
	
	rabin_karp(s,t);
	
	g<<nr<<endl;
	for(int i=0;i<min(NR_POZ,nr);i++)
		g<<poz[i]<<" ";
	g.close();
}