Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ui64 = unsigned long long;
- using ui32 = unsigned int;
- const ui64 BASE = 123;
- const ui64 MOD = 1791791791;
- const ui32 MAXLEN = 30;
- vector <ui64> calculate_pws() {
- vector <ui64> ans(MAXLEN + 1);
- ans[0] = 1;
- for (ui32 i = 1; i <= MAXLEN; ++i) {
- ans[i] = ans[i - 1] * BASE % MOD;
- }
- return ans;
- }
- const vector<ui64> PWS = calculate_pws();
- inline void addSymbolToHash(ui64 &hash, char symb) {
- hash = (hash * BASE + symb) % MOD;
- }
- inline void removeSymbolFromHash(ui64 &hash, ui32 length, char symb) {
- hash = ((hash - symb * PWS[length - 1]) % MOD + MOD) % MOD;
- }
- inline ui64 calculate_hash(const string& s) {
- ui64 hash = 0;
- for (const auto& ch: s) {
- addSymbolToHash(hash, ch);
- }
- return hash;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout.setf(ios::fixed);
- cout.precision(10);
- string t;
- cin >> t;
- ui32 n;
- cin >> n;
- vector <unordered_map<ui64, ui32> > hashes(MAXLEN + 1);
- unordered_set<ui32> lengths;
- for (ui32 i = 0; i < n; ++i) {
- string s;
- cin >> s;
- hashes[s.size()][calculate_hash(s)] = i;
- lengths.insert(s.size());
- }
- ui64 current_hash = 0;
- unordered_map<ui32, ui64> length_to_hash;
- vector <int> answer(n, 0);
- auto check_answer = [&answer, &hashes](ui32 length, ui64 hash) {
- if (length <= MAXLEN) {
- const auto& it = hashes[length].find(hash);
- if (it != hashes[length].end()) {
- answer[it->second] = 1;
- }
- }
- };
- for (ui32 i = 0; i < t.size(); ++i) {
- for (auto &[length, hash]: length_to_hash) {
- removeSymbolFromHash(hash, length, t[i - length]);
- addSymbolToHash(hash, t[i]);
- check_answer(length, hash);
- }
- addSymbolToHash(current_hash, t[i]);
- if (lengths.find(i + 1) != lengths.end()) {
- length_to_hash[i + 1] = current_hash;
- }
- check_answer(i + 1, current_hash);
- }
- for (auto& i: answer) {
- if (i == 0) {
- cout << "No\n";
- } else {
- cout << "Yes\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement