Cod sursa(job #800998)

Utilizator vlad96Vlad Zuga vlad96 Data 23 octombrie 2012 00:18:19
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<string.h>
#include<stdio.h>
#include<vector>

using namespace std;

#define MOD 50021
#define MAXL 10000005
#define MAXP 30

long long pw[MAXP];
long long aux, x;
vector<long long> v[MOD];
int n, i, b=3, res, m, o;
char s[MAXL], p[MAXP];

inline int search (x)
{
	int list = x%MOD;
	vector<int>::iterator it;
	for ( it = v[list].begin(); it != v[list].end(); ++ it)
		if ( *it == x )
			return 1;
	return 0;
}

inline void insert (x)
{
	int list = x%MOD;
	v[list].push_back(x);
}

int main ()
{
	pw[0] = 1;
	for ( i = 1; i <= 22; i ++ )
		pw[i] = b*pw[i-1];
	
	FILE *fis = fopen ("abc2.in", "r");
	fgets(s, 10000005, fis);
	n = strlen(s)-2;
	
	fgets(p, 30, fis);
	o = strlen(p)-2;
	
	while (!feof(fis))
	{
		if ( strlen(p)-2 == m )
		{
			aux = 0;
			for ( i = 0; i <= m; i ++ )
				aux = aux * b + p[i] - 'a';
			if ( search(aux) != 1 )
				insert(aux);
		}
		fgets(p, 30, fis);
	}
	
	fclose(fis);
	
	aux = 0;
	for ( i = 0; i <= m; i ++ )
		aux = aux * b + s[i] - 'a';
	
	res += search(x);
	
	for ( i = m+1; i <= n; i ++ )
	{
		aux = ( aux - s[i-m-1] - 'a') * pw[m] * b + s[i] - 'a';
		res += search(x);
	}
	
	FILE *fis2 = fopen("abc2.out", "w");
	fprintf(fis2, "%d\n", res);
	fclose(fis2);
	
	return 0;
}