Cod sursa(job #103892)

Utilizator peanutzAndrei Homorodean peanutz Data 15 noiembrie 2007 18:59:52
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.42 kb
#include <stdio.h>
#include <vector>
#include <set>

using namespace std;

#define pb push_back
#define MOD 666013
#define NMAX 10000010

#define DIM 2000000
int poz;
char buf[DIM];

inline long long f(int n)
{
	if(n == 0) return 1;
	long long p = 1;
	for(int i = 1; i < n; ++i)
		p = (long long)p * 3;
	return p;
}

char s[NMAX], c[21];
int n;
long long res;
set<long long> h[MOD];

void read()
{
    long long x;
    short ok;
    while(poz < DIM)
    {
    x = 0; ok = 0;
	for(int i = 0; i < n; ++i)
	{
     	if(buf[poz] >= 'a' && buf[poz] <= 'c')
		{
             x = (long long)x*3 + (buf[poz]-'a');
             ok = 1;
             ++poz;
		}
        else break;
    }
    ++poz;
//    if(ok) printf("%d\n", x);
	if(ok) h[x % MOD].insert(x);
    }
}

int main()
{
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);

	scanf("%s\n", s);
	fread(buf, 1, DIM, stdin);
    for(; buf[n] >= 'a' && buf[n] <= 'c';) ++n;

    read();

	long long t = 0, p = f(n);
	for(int i = 0; i < n; ++i)
		t = (long long)t*3 + (s[i]-'a');

	set<long long> :: iterator it;
	long long until = strlen(s)-n, aux;
	for(int i = 0; i <= until; ++i)
	{
		aux = t % MOD;//  printf("%d\n", t);
		
		if(h[aux].find(t) != h[aux].end())
			++res;

       		t = (long long)t - p*(s[i]-'a');
       		t = (long long)t*3 + (s[i+n]-'a');
	}
	printf("%lld\n", res);
	return 0;
}