Pagini recente » Cod sursa (job #2042054) | Cod sursa (job #3252927) | Cod sursa (job #1007671) | Cod sursa (job #2418846) | Cod sursa (job #1842272)
#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';
}
long long hashString(const string& str){
long long s = 0;
long long 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){
long long 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;
}