Cod sursa(job #781149)

Utilizator visanrVisan Radu visanr Data 23 august 2012 19:46:10
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

#define modulo 50021

char S[10000010], ss[50];
unsigned int v[90910];
vector<unsigned int> Hash[modulo];


int Check(unsigned int A, int B)
{
    unsigned int aux = A % modulo;
    if(find(Hash[aux].begin(), Hash[aux].end(), A) != Hash[aux].end()) return 1;
    if(B) Hash[aux].push_back(A);
    return 0;
}

int main()
{
    freopen("abc2.in", "r", stdin);   
    freopen("abc2.out", "w", stdout);
    unsigned int N, M, i, j, aux, sol = 0, X = 0; 
    S[0] = 'a';
    fgets(S + 1, 10000005, stdin);
    N = strlen(S) - 2;
    fgets(ss, 45, stdin);
    M = strlen(ss) - 1;
    for(i = 0; i < M; i++)
          v[1] = v[1] * 3 + ss[i] - 'a';
    Check(v[1], 1);
    i = 1;
    while(!feof(stdin))
    {
                       i ++;
                       fgets(ss, 45, stdin);
                       for(j = 0; j < M; j++)
                             v[i] = v[i] * 3 + ss[j] - 'a';
                       Check(v[i], 1);
    }
    aux = 1;
    X = 0;
    for(i = 1; i < M; i++) 
          aux *= 3, X = X * 3 + S[i] - 'a';
    for(j = 1; j <= N - M + 1; j++)
    {
            X = (X - (S[j - 1] - 'a') * aux) * 3 + S[j + M - 1] - 'a';
            if(Check(X, 0)) sol ++;
    }
    printf("%u\n", sol);
    return 0;
}