Cod sursa(job #265586)

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

using namespace std;

typedef long long  LL;

const LL BASE = 3;

char text[10000001];
LL dic[50022];

int check(LL X) {
    int left = 1, right = dic[0];
    while (left <= right) {
          int mid = (left + right) >> 1;
          if (dic[mid] == X) return 1;
          if (dic[mid] > X) right = mid - 1;
          else left = mid + 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');
             
              }
          dic[++dic[0]] = idx;
          }
    int total = 0;
    sort(dic + 1, dic + dic[0] + 1);
    //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;
    }