Cod sursa(job #265581)

Utilizator vlad_DVlad Dumitriu vlad_D Data 24 februarie 2009 05:49:01
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>

using namespace std;

typedef long long  LL;

const LL BASE = 3;
const LL M = 97957LL;//969LL;

bool Hash1[100000];

char text[10000001];
int check(int X) {
    if (Hash1[X]) return 1;
    return 0;
    }
int main() {
    ifstream fin("abc2.in");
    ofstream fout("abc2.out");
    
    fin >> text;
    
    char word[21];
    int m = 0;
    while (fin >> word) {
          LL idx = 0;
          m = 0;
          for (int i = 0; word[i]; ++i, ++m) idx*=BASE, idx+=(word[i]-'a'), idx%=M;
          Hash1[idx] = true;
          }
    int total = 0;
    
    //adauga
    LL number = 0;
    LL BB = 1;
    for (int i = 1; i < m; ++i) BB*=BASE, BB%=M;
    for (int i = 0; i < m; ++i) number*=BASE, number+=text[i]-'a', number%=M;
    
    
    total+=check(number);
    
    for (int i = m; text[i]; ++i) {
        number+=M; number-=BB * (text[i-m]-'a'); number%=M;
        number*=BASE; number+=text[i] - 'a'; number%=M; 
        total+=check(number);
        }
    
    fout << total << '\n';        
    return 0;
    }