Cod sursa(job #854753)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 13 ianuarie 2013 22:54:36
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
// Rabin - Karp

#include <fstream>
#include <cstring>
#define base 59
using namespace std;

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

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

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]);
		n++;
	}
	
	basepow=1;
	for (i=1; i<n; i++) basepow*=base;

	
	for (i=0; i<n; i++){
		keyb=keyb*base+convertLetter(b[i]);
	}
	
	if (keya==keyb) rez[++rezt]=0;
	
	for (i=n; b[i]!='0'; i++){
		keyb=(keyb - basepow * convertLetter(b[i-n]) )*base + convertLetter(b[i]);
		if (keya==keyb) rez[++rezt]=i-n+1;
	}
	
	g<<rezt<<"\n";
	for (i=1; i<=rezt; i++) g<<rez[i]<<" ";
	
		
}