Cod sursa(job #854786)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 14 ianuarie 2013 00:25:46
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
// Rabin - Karp

#include <fstream>
#include <cstring>
using namespace std;

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

const int base=59;
const int nmod1=100003, nmod2=100019;

char a[2000005], b[2000005];
int rez[2000005];
int i, j, n, m, rezt;
int keya, keyb, basepow, keya2, keyb2, basepow2;

inline int convertLetter (char c){
	if (c<'a') return c-'A';
	return c-'a'+26;
}

int main(){
	f>>a>>b;
	for (i=0; a[i]!='\0'; i++){
		keya=(keya*base+convertLetter(a[i])) % nmod1;
		keya2=(keya2*base+convertLetter(a[i])) % nmod2;
		n++;
	}
	
	basepow=basepow2=1;
	for (i=1; i<n; i++) {
		basepow=basepow * base % nmod1;
		basepow2=basepow2 * base % nmod2;
	}

	
	for (i=0; i<n; i++){
		keyb=(keyb*base+convertLetter(b[i])) % nmod1;
		keyb2=(keyb2*base+convertLetter(b[i])) % nmod2;
	}
	
	if (keya==keyb && keya2 == keyb2) rez[++rezt]=0;
	
	for (i=n; b[i]!='0'; i++){
		keyb=(((keyb - (basepow*convertLetter(b[i-n])%nmod1) + nmod1) * base + convertLetter(b[i]))) % nmod1;
		keyb2=(((keyb2 - (basepow2*convertLetter(b[i-n])%nmod2) + nmod2) * base + convertLetter(b[i]))) % nmod2;
		if (keya==keyb && keya2 == keyb2) rez[++rezt]=i-n+1;
	}
	
	g<<rezt<<"\n";
	for (i=1; i<=rezt && i<=1000; i++) g<<rez[i]<<" ";
	
		
}