Pagini recente » Cod sursa (job #382879) | Cod sursa (job #1674533) | Cod sursa (job #1636042) | Cod sursa (job #544005) | Cod sursa (job #2300813)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
const int mod = 10041, N = 10001010, M = 30;
unsigned int n, len_cuv, len_text, x, i, cnt, nr, pow;
char text[N], cuv[M];
vector<unsigned int> L[mod + 10];
void hashing() {
x = 0;
for (i = 0 ; i < len_cuv; ++i) {
x = x * 3 + (cuv[i] - 'a');
}
if (x == 0) {
nr = 0;
} else {
nr = x % mod;
}
for (auto it:L[nr]) {
if (it == x){
return;
}
}
L[nr].push_back(x);
}
void verifica(int x) {
if (x == 0) {
nr = 0;
} else {
nr = x % mod;
}
if (nr < 0) {
exit(0);
}
for (auto it:L[nr]) {
if (it == x){
cnt++;
return;
}
}
}
int main() {
fin >> text;
len_text = strlen(text);
fin >> cuv;
len_cuv = strlen(cuv);
hashing();
while(fin >> cuv) {
hashing();
}
x = 0;
pow = 1;
for(i = 1; i < len_cuv; ++i) {
pow = pow * 3;
}
for(i = 0; i < len_cuv - 1; ++i) {
x = x * 3 + (text[i] - 'a');
}
for(i = len_cuv - 1; i < len_text; ++i) {
x = x * 3 + (text[i] - 'a');
verifica(x);
x = x - pow * (text[i - len_cuv + 1] - 'a');
}
fout << cnt;
return 0;
}