Pagini recente » Cod sursa (job #1345757) | Cod sursa (job #2931092) | Cod sursa (job #2322829) | Cod sursa (job #2589192) | Cod sursa (job #956695)
Cod sursa(job #956695)
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
const int N = 50005;
const int MOD = 666013;
const int LEN = 25;
int n, m;
string text;
vector <int> Hash[MOD];
/*void init() {
power[0] = 1;
for (int i = 1; i <= LEN; ++i)
power[i] = (power[i - 1] * BASE) % MOD;
}*/
void insert(string s) {
int h = 0;
for (int i = 0; i < s.size(); ++i)
h = h * 3 + s[i] - 'a';
Hash[h % MOD].push_back(h);
}
bool exist(int x) {
for (int i = 0; i < Hash[x % MOD].size(); ++i)
if (Hash[x % MOD][i] == x)
return true;
return false;
}
void read() {
f >> text;
n = text.size();
string s;
while (f >> s) {
//g << s << '\n';
m = s.size();
insert(s);
}
}
void solve() {
int sol = 0;
if (n < m) {
g << "0\n";
return;
}
int h = 0, power = 1;
for (int i = 0; i < m; ++i) {
h = h * 3 + text[i] - 'a';
if (i < m - 1)
power *= 3;
}
if (exist(h))
++sol;
for (int i = m; i < n; ++i) {
h -= power * (text[i - m] - 'a');
h = h * 3 + (text[i] - 'a');
if (exist(h))
++sol;
}
g << sol << '\n';
}
int main() {
//init();
read();
solve();
}