Cod sursa(job #1842269)

Utilizator horatiucheval2Horatiu Andrei Cheval horatiucheval2 Data 6 ianuarie 2017 19:10:20
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

const int M = 698471;
vector<string> table[M];

int code(char c){
    return c - 'a';
}

int hashString(const string& str){
    int s = 0;
    int p = 1;
    for(int i = 0; i < str.length(); i++){
        s += p * code(str[i]);
        p *= 3;
    }
    return s;
}

int main(){
    ifstream fin("abc2.in");
    ofstream fout("abc2.out");

    string text, temp;
    int len, k = 0;
    fin >> text;

    while(fin >> temp){
        int h = hashString(temp);
        table[h % M].push_back(temp);
        len = temp.length();
    }

    int h = hashString(text.substr(0, len));
    for(int j = 0; j < table[h % M].size(); j++){
        if(table[h % M][j] == text.substr(0, len)){
            k++;
            break;
        }
    }
    for(int i = len; i < text.length(); i++){
        h = (h - code(text[i - len])) / 3 + pow(3, len - 1) * code(text[i]);
        for(int j = 0; j < table[h % M].size(); j++){
            if(table[h % M][j] == text.substr(i - len + 1, len)){
                k++;
                break;
            }
        }
    }

    fout <<k;


    fin.close();
    fout.close();
    return 0;
}