Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <cmath>
- #include <map>
- using namespace std;
- using ll = long long;
- using ull = unsigned long long;
- map<string, bool> ans;
- string s;
- struct Node {
- Node* next[26];
- bool term; //терминальная ли
- Node() {
- for(int i = 0; i < 26; i++) {
- next[i] = nullptr;
- }
- term = false;
- }
- Node(string& w, char c) {
- for(int i = 0; i < 26; i++) {
- next[i] = nullptr;
- }
- term = true;
- word = w + c;
- }
- string word = "";
- };
- struct Trie {
- Node* root;
- Trie() {
- root = new Node();
- }
- void insert(string &s) {
- Node* cur = root;
- for(int i = 0; i < s.length(); i++) {
- char c = s[i];
- if (cur->next[c - 'a'] == nullptr) {
- cur->next[c - 'a'] = new Node();
- }
- cur->next[c - 'a']->word = cur->word + c;
- cur = cur->next[c - 'a'];
- }
- cur->term = true;
- }
- bool find(int suff) {
- Node* cur = root;
- for(int i = 0; suff + i < s.length(); i++) {
- cur = cur->next[s[suff + i] - 'a'];
- if (cur == nullptr) return false;
- if (cur->term) {
- ans[cur->word] = true;
- }
- }
- return cur->term;
- }
- };
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> s;
- int M; cin >> M;
- vector<string> vec(M);
- Trie trie;
- for(int i = 0; i < M; i++) {
- cin >> vec[i];
- trie.insert(vec[i]);
- }
- for(int i = 0; i < s.length(); i++) {
- trie.find(i);
- }
- for(int i = 0; i < M; i++) {
- if (ans[vec[i]]) cout << "Yes\n";
- else cout << "No\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement