Pagini recente » Cod sursa (job #542263) | Cod sursa (job #3293608) | Cod sursa (job #374420) | Istoria paginii problema/produse | Cod sursa (job #1489481)
#include <bits/stdc++.h>
using namespace std;
const char iname[] = "abc2.in";
const char oname[] = "abc2.out";
const unsigned int MOD = 666013, BASE = 3;
int n = 0, lenght, textLenght, wordLenght, ans;
char text[10000100], word[25];
vector<unsigned int> H[MOD];
unsigned int pow3(int p){
unsigned int rez = 1, val = BASE;
while(p != 0){
if(p & 1) rez *= val;
val *= val;
p >>= 1;
}
return rez;
}
bool SearchHash(unsigned int val){
int poz = val % MOD;
int sz = H[poz].size();
for(int i = 0; i < sz; ++i)
if(H[poz][i] == val)
return true;
return false;
}
void read(){
freopen(iname, "r", stdin);
scanf("%s", text);
while(scanf("%s", word) == 1){
wordLenght = strlen(word);
unsigned int reprez = 0;
for(int i = 0; i < wordLenght; ++i) reprez = reprez * BASE + (word[i] - 'a');
if(!SearchHash(reprez))
H[reprez%MOD].push_back(reprez);
}
}
int main(){
read();
textLenght = strlen(text);
unsigned int reprez = 0;
if(wordLenght <= textLenght)
for(int i = 0; i < wordLenght; ++i){
reprez = reprez * BASE + (text[i]-'a');
}
if(SearchHash(reprez)) ++ans;
for(int i = wordLenght; i < textLenght; ++i){
reprez = BASE * (reprez - pow3(wordLenght-1)*((text[i-wordLenght] - 'a'))) + (text[i] - 'a');
if(SearchHash(reprez)) ++ans;
}
freopen(oname,"w", stdout);
printf("%d", ans);
return 0;
}