Cod sursa(job #1216488)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 4 august 2014 17:50:44
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <stdio.h>
using namespace std;
typedef unsigned int uint;

uint fail[2000000 + 5],n,m,poz[1001],base = 123;
const uint mod1 = 10009,mod2 = 10007;
char p[2000000 + 10],w[2000000 + 10];
inline uint hashF(char w[],uint sz,const uint mod){
	uint res = 0;
	for(uint i = 0; i < sz - 1; i++)
		res = ((res + (uint)(w[i])) * base) % mod;
	res = (w[sz - 1] + res) % mod;
	return res;
}
inline uint modPow(uint a, uint b,const uint mod){
	uint res = 1;
	while(b){
		if(b & 1)
			res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}
inline uint reHashF(uint start,int res,uint addPow, uint mod){
	res = res - ((int)w[start] * (int)addPow) % (int)mod;
	while(res < 0)
		res += (int)mod;
	res = (res * (int)base) % (int)mod;
	res += (int)w[start + m] % (int)mod;
	return res % (int)mod;
}
bool checkEq(uint start){
	for(uint i = 0; i < m; i++)
		if(p[i] != w[i + start])
			return false;	
	return true;
}
void RK(){
	uint c = 0,currentPow1 = modPow(base,m - 1,mod1),currentPow2 = modPow(base,m - 1,mod2);
	uint patHash1 = hashF(p,m,mod1),wordHash1 = hashF(w,m,mod1),patHash2 = hashF(p,m,mod2),wordHash2 = hashF(w,m,mod2);
	for(uint i = 0; i < n - m; i++){
		if(patHash1 == wordHash1 && patHash2 == wordHash2){
			if(c < 1000){
				poz[c] = i;
			}
			c++;				
		}
		wordHash1 = reHashF(i,(int)wordHash1,currentPow1,mod1);
		wordHash2 = reHashF(i,(int)wordHash2,currentPow2,mod2);
	}
	uint min = c > 1000 ? 1000 :  c;
	printf("%u\n",c);
	for(uint i = 0; i < min; i++)
		printf("%u ", poz[i]);

}

int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	fgets(p,sizeof(p),stdin);
	fgets(w,sizeof(w),stdin);
	for(; p[m] > 0; m++);
	m--;
	for(; w[n] > 0; n++);
	RK();
	return 0;
}