Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_map>
- #include <string>
- #include <map>
- #define ll long long
- #define len(v) (int)v.size()
- #define all(v) v.begin(), v.end()
- using namespace std;
- struct para {
- ll x;
- ll y;
- };
- ll p1 = 29, p2 = 239, m = 2e5 + 3;
- bool operator==(const para& a, const para& b) {
- return a.x == b.x && a.y == b.y;
- }
- namespace std {
- template <>
- struct hash<para> {
- std::size_t operator()(const para& k) const
- {
- return (k.x + k.y) % m;
- }
- };
- }
- string t;
- unordered_map<para, int> words;
- para geth(string s) {
- ll h1 = 0;
- for (int i = 0; i < len(s); ++i) {
- h1 = ((h1 * p1) % m + (s[i] - 'a' + 1)) % m;
- }
- ll h2 = 0;
- for (int i = 0; i < len(s); ++i) {
- h2 = ((h2 * p2) % m + (s[i] - 'a' + 1)) % m;
- }
- return {h1, h2};
- }
- void addword(string s, int key) {
- para Hash = geth(s);
- while (words[Hash] != 0) {
- Hash.x = (Hash.x + 1) % m;
- Hash.y = (Hash.y + 1) % m;
- }
- words[Hash] = key;
- }
- vector<string> str;
- int srch(string s) {
- para Hash = geth(s);
- if (str[words[Hash]] == s) return words[Hash];
- if (words[Hash] == 0) return -1;
- while (words[Hash] != 0 || str[words[Hash]] != s) {
- Hash.x = (Hash.x + 1) % m;
- Hash.y = (Hash.y + 1) % m;
- }
- if (str[words[Hash]] == s) return words[Hash];
- if (words[Hash] == 0) return -1;
- }
- int q;
- void solve() {
- cin >> t >> q;
- str.resize(q + 1);
- //vector<string> str(q + 1);
- for (int i = 1; i <= q; ++i) {
- string a;
- cin >> a;
- str[i] = a;
- addword(a, i);
- }
- vector<bool> res(q);
- for (int i = 0; i < len(t); ++i) {
- string tmp = "";
- for (int k = 0; (k <= 30 && (i + k) < len(t)); ++k) {
- tmp += t[i + k];
- int n = srch(tmp);
- if (n > -1) res[n - 1] = true;
- }
- }
- for (auto el : res) {
- cout << (el == 1 ? "Yes\n" : "No\n");
- }
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment