Nu aveti permisiuni pentru a descarca fisierul grader_test4.in
Cod sursa(job #2295890)
Utilizator | Data | 4 decembrie 2018 00:03:22 | |
---|---|---|---|
Problema | Abc2 | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.98 kb |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
gp_hash_table<int, int> table;
const int kBase = 28;
int Compute(const string& s) {
int n = s.size(); int ret = 0;
for (int i = 0; i < n; ++i) {
ret = ret * kBase + s[i];
}
return ret;
}
int main() {
ifstream cin("abc2.in");
ofstream cout("abc2.out");
vector <int> pats;
string s; cin >> s;
int l = -1;
string p;
while (cin >> p) {
l = p.size();
table[Compute(p)] = 1;
}
int ans = 0;
int pw = 1;
for (int i = 1; i < l; ++i)
pw = pw * kBase;
int has = 0;
for (int i = 0; i < (int)s.size(); ++i) {
has = has * kBase + s[i];
if (i + 1 >= l) {
ans += table.find(has) != table.end();
has -= pw * s[i - l + 1];
}
}
cout << ans << endl;
return 0;
}