Cod sursa(job #512283)

Utilizator cosmyoPaunel Cosmin cosmyo Data 13 decembrie 2010 19:33:22
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <cstring>
using namespace std;
const int N = 10000005;
const int B1 = 3;
const int B2 = 5;
const int P1 = 666013;
const int P2 = 100007;
char s[N], t[50001][25],x[P1],y[P2];
int n, a, b, m;

int min( int a, int b ) {
	return a<b?(a):(b);
}

int main() {
	ifstream fin("abc2.in");
	ofstream fout("abc2.out");
	int i, r, nr = 0, val1, val2, j;
		fin.getline(s,N);
		
		while( !fin.eof()) {
			++n;
			fin.getline(t[n],25);
//			fout<<t[n]<<'\n';
		}
		--n;
	val1 = 1;
	val2 = 1;
	r = strlen(t[1]);
	for(i = 1 ; i < r; ++i){
		val1 = (val1 * B1) % P1;
		val2 = (val2 * B2) % P2;
	}
	for( i = 1; i <= n; ++i) {
		a = b = 0;
		for( j = 0; j < r; ++j) {
			a = ( a * B1 + t[i][j] - 'a' + 1) % P1;
			b = ( b * B2 + t[i][j] - 'a' + 1) % P2;
		}
		x[a] = 1;y[b] = 1;
	//	fout<<a<<" "<<b<<'\n';
	}
	a = 0;
	b = 0;
//	fout<<val1<<" "<<val2<<" "<<B1<<" "<<B2<<" "<<P1<<" "<<P2<<'\n';
	for( i = 0; i < r; ++i) {
		a = ( a * B1 + s[i] - 'a' + 1) % P1;
		b = ( b * B2 + s[i] - 'a' + 1) % P2;
	}
	m = strlen(s);
	
	for( i = r; i <= m ; ++i) {
		if(  x[a] && y[b])
			++nr;
//		fout<<a<<" "<<b<<'\n';
		a = (a - (s[i - r] - 'a' + 1) * val1 ) % P1 + P1; a = (a * B1 + s[i] - 'a' +1) % P1;
		b = (b - (s[i - r] - 'a' + 1) * val2 ) % P2 + P2; b = (b * B2 + s[i] - 'a' +1) % P2;
	}
	
	fout<<nr<<'\n';
	fin.close();
	fout.close();

  return 0;

}