Cod sursa(job #512312)

Utilizator cosmyoPaunel Cosmin cosmyo Data 13 decembrie 2010 19:48:02
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 10000005;
const int B1 = 3;
const int P1 = 666013;
char s[N], t[50001][25];
typedef unsigned int ui;
ui n, a, b, m;
vector<ui> x[P1 + 10];


int main() {
	ifstream fin("abc2.in");
	ofstream fout("abc2.out");
	ui i, r, nr = 0, val1 = 1, val2 = 1, j;
		fin.getline(s,N);
		
		while( !fin.eof()) {
			++n;
			fin.getline(t[n],25);
		}
		--n;
	val1 = 1;
	r = strlen(t[1]);
	for(i = 1 ; i < r; ++i) {
		val1 = (val1 * B1) % P1;
		val2 = val2 * B1;
	}
	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 * B1 +t[i][j] -'a' + 1;
		x[a].push_back(b);
	}
	a = 0;
	b = 0;
	for( i = 0; i < r; ++i) {
		a = ( a * B1 + s[i] - 'a' + 1) % P1;
		b = ( b * B1 + s[i] - 'a' + 1); 
	}	
		m = strlen(s);
   s[m] = 'a';
	for( i = r; i <= m ; ++i) {
		for( j = 0; j < x[a].size(); ++j)
			if(x[a][j] == b) {
				++nr;
				break;
			}
				 
		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); b = (b * B1 + s[i] - 'a' + 1); 
	}
	
	fout<<nr<<'\n';
	fin.close();
	fout.close();

  return 0;

}