fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <map>
  5. #include <algorithm>
  6. #include <queue>
  7. #include <cstring>
  8.  
  9. using namespace std;
  10.  
  11. class Node
  12. {
  13. public:
  14. 	map<char,Node*> children;
  15. 	bool islast;
  16. 	Node* fail;
  17. 	int id;
  18.  
  19. 	Node(int i)
  20. 	{
  21. 		islast = false;
  22. 		fail = NULL;
  23. 		id = i;
  24. 	}
  25.  
  26. };
  27.  
  28. class trie
  29. {
  30. public:
  31. 	Node* root;
  32. 	bool exist[1005];
  33. 	vector<char> alpha;
  34. 	bool vis[256];
  35.  
  36. 	trie(vector<string> p)
  37. 	{
  38. 		root = new Node(-1);
  39. 		memset(exist,false,sizeof(exist));
  40. 		memset(vis,false,sizeof(vis));
  41. 		insert_patterns(p);
  42. 		automaton();
  43. 	}
  44.  
  45. 	bool contains(map<char,Node*> m, char c)
  46. 	{
  47. 		return m.find(c) != m.end();
  48. 	}
  49.  
  50. 	void insert(string s, int id)
  51. 	{
  52. 		Node* c = root;
  53.  
  54. 		for(int i=0;i<s.size();i++)
  55. 		{
  56. 			if(!vis[s[i]])
  57. 			{
  58. 				vis[s[i]] = true;
  59. 				alpha.push_back(s[i]);
  60. 			}
  61.  
  62. 			if(contains(c->children,s[i]))
  63. 			{
  64. 				c = c->children[s[i]];
  65. 			}
  66. 			else
  67. 			{
  68. 				c->children[s[i]] = new Node(id);
  69. 				c = c->children[s[i]];
  70. 			}
  71. 		}
  72.  
  73. 		c->islast = true;
  74. 	}
  75.  
  76. 	void insert_patterns(vector<string> p)
  77. 	{
  78. 		for(int i=0;i<p.size();i++)
  79. 			insert(p[i],i);
  80. 	}
  81.  
  82. 	void automaton()
  83. 	{
  84.  
  85. 		queue<Node*> q;
  86.  
  87. 		for(int i=0;i<alpha.size();i++)
  88. 		{
  89.  
  90. 			if(!contains(root->children,alpha[i]))
  91. 			{
  92. 				root->children[alpha[i]] = root;
  93. 			}
  94. 			else
  95. 			{
  96. 				q.push(root->children[alpha[i]]);
  97. 				root->children[alpha[i]]->fail = root;
  98. 			}
  99. 		}
  100.  
  101. 		while(q.size())
  102. 		{
  103. 			Node* p = q.front();
  104. 			q.pop();
  105.  
  106. 			map<char,Node*>::iterator it = p->children.begin();
  107. 			for(;it!=p->children.end();it++)
  108. 			{
  109. 				char ch = it->first;
  110. 				Node* u = it->second;
  111.  
  112. 				q.push(u);
  113.  
  114. 				Node* v = p->fail;
  115. 				while(!contains(v->children,ch))
  116. 				{
  117. 					v = v->fail;
  118. 				}
  119.  
  120. 				u->fail = v->children[ch];
  121.  
  122. 			}
  123.  
  124. 		}
  125.  
  126. 	}
  127.  
  128. 	void search(string s)
  129. 	{
  130. 		Node* cur = root;
  131.  
  132. 		for(int i=0;i<s.size();i++)
  133. 		{
  134.  
  135. 			if(!vis[s[i]])
  136. 			{
  137. 				vis[s[i]]= true;
  138. 				alpha.push_back(s[i]);
  139. 				root->children[s[i]] = root;
  140. 			}
  141.  
  142. 			while(!contains(cur->children,s[i]))
  143. 			{
  144. 				cur = cur->fail;
  145. 			}
  146.  
  147. 			cur = cur->children[s[i]];
  148.  
  149. 			if(cur->islast)
  150. 			{
  151. 				Node* tem = cur;
  152. 				while(tem!= root)
  153. 				{
  154. 					if(tem->islast)
  155. 					{
  156. 						exist[tem->id] = true;
  157.  
  158. 					}
  159.  
  160. 					tem = tem->fail;
  161.  
  162. 				}
  163. 			}
  164.  
  165. 		}
  166. 	}
  167.  
  168. };
  169.  
  170. int main()
  171. {
  172.  
  173. 	int n;
  174. 	cin >> n;
  175.  
  176. 	while(n--)
  177. 	{
  178. 		string s;
  179. 		cin >> s;
  180.  
  181. 		int q;
  182. 		cin >> q;
  183. 		vector<string> p;
  184.  
  185. 		map<string,int> vis;
  186.  
  187. 		int id = 0;
  188. 		while(q--)
  189. 		{
  190. 			string ss;
  191. 			cin >> ss;
  192.  
  193. 			if(vis.find(ss) == vis.end())
  194. 			{
  195. 				vis[ss] = id;
  196. 			}
  197.  
  198. 			id++;
  199. 			p.push_back(ss);
  200. 		}
  201.  
  202. 		trie* t = new trie(p);
  203.  
  204. 		t->search(s);
  205.  
  206. 		for(int i=0;i<p.size();i++)
  207. 		{
  208. 			string r = t->exist[vis[p[i]]] ? "y" : "n";
  209. 			cout << r << endl;
  210. 		}
  211.  
  212. 	}
  213.  
  214. 	system("pause");
  215.  
  216.  
  217. }
  218.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
1
taken
4
taken
take
ake
ke
stdout
copy 
y
n
y
y
https://ideone.com/Tblbi
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!