Cod sursa(job #265582)

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

using namespace std;

typedef long long  LL;

const LL BASE = 3;
const LL M = 97957LL;//969LL;
const LL M2 = 99987LL;
bool Hash1[100000];
bool Hash2[100000];
char text[10000001];
int check(int X, int Y) {
    if (Hash1[X] && Hash2[Y]) 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;
          LL idx2 = 0 ;
          m = 0;
          for (int i = 0; word[i]; ++i, ++m) {
              idx*=BASE, idx+=(word[i]-'a'), idx%=M;
              idx2*=BASE, idx2+=(word[i]-'a'), idx2%=M2;
              }
          Hash1[idx] = true;
          Hash2[idx2] = true;
          }
    int total = 0;
    
    //adauga
    LL number = 0;
    LL num2 = 0;
    LL BB = 1;
    LL BB2 = 1;
    for (int i = 1; i < m; ++i) BB*=BASE, BB%=M, BB2*=BASE, BB2%=M2;
    for (int i = 0; i < m; ++i) { 
        number*=BASE, number+=text[i]-'a', number%=M;
        num2*=BASE, num2+=text[i]-'a', num2%=M2;
        }
    
    
    total+=check(number, num2);
    
    for (int i = m; text[i]; ++i) {
        num2+=M2; num2-=BB2 * (text[i-m]-'a'), num2%=M2;
        number+=M; number-=BB * (text[i-m]-'a'); number%=M;
        
        num2*=BASE, num2+=text[i]-'a', num2%=M;
        number*=BASE; number+=text[i] - 'a'; number%=M; 
        
        total+=check(number, num2);
        }
    
    fout << total << '\n';        
    return 0;
    }