Cod sursa(job #265588)

Utilizator vlad_DVlad Dumitriu vlad_D Data 24 februarie 2009 06:23:44
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
//HASHing

#include <fstream>

using namespace std;

typedef long long  LL;

const LL BASE = 3;

char text[10000001];
struct nod {
       LL val;
       nod *next;
       };
typedef nod* nodP;       
const LL M = 99987;
nodP Hash[100000];

void addHash(LL X) {
     LL key = X % M;
     nodP nou = new nod;
     nou->val = X; nou->next = Hash[key];
     Hash[key] = nou;
     }
int check(LL X) {
    LL key = X % M;
    nodP nou = Hash[key];
    while (nou != NULL) {
          if (nou -> val == X) return 1;
          nou = nou->next;
          }
    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');
             
              }
          addHash(idx);
          
          }
    int total = 0;
    //adauga
    LL number = 0;
 
    LL BB = 1;
 
    for (int i = 1; i < m; ++i) BB*=BASE;
    for (int i = 0; i < m; ++i) { 
        number*=BASE, number+=text[i]-'a';
        }
    
    
    total+=check(number);
    
    for (int i = m; text[i]; ++i) {
        number-= (BB * (text[i-m]-'a'));
        number*=BASE; number+=text[i] - 'a';
        
        total+=check(number);
        }
    
    fout << total << '\n';        
    return 0;
    }