Cod sursa(job #2755386)

Utilizator Mirc100Mircea Octavian Mirc100 Data 27 mai 2021 01:36:38
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 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' && t[i]>='A')
        	hash_t[i+1] = (hash_t[i] + (t[i] - 'A' + 1) * p_pow[i]) % m; 
        else
        	if(t[i]<='z' && t[i]>='a')
        		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] - '0' + 1) * p_pow[i]) % m; 
    int hash_s = 0; 
    for (int i = 0; i < ns; i++) {
	        if(s[i]<='Z' && s[i]>='A')
				hash_s = (hash_s + (s[i] - 'A' + 1) * p_pow[i]) % m; 
			else
				if(s[i]<='z' && s[i]>='a')
					hash_s = (hash_s + (s[i] - 'a' + 1) * p_pow[i]) % m; 
				else
			 		hash_s = (hash_s + (s[i] - '0' + 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();
}