fork download
copy 
  1. /*
  2.     Hi. This is my current implementation for Aho-Corasick suffix automaton.
  3.     The example below is for problem https://o...content-available-to-author-only...s.com/problems/stringmultimatching
  4.     However, I couldn't get it working, as I always get Wrong Answer when submitting with this code.
  5.     Can you help me debug this code? Thanks.
  6. */
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. #include <ext/pb_ds/tree_policy.hpp>
  11. using namespace __gnu_pbds;
  12. #define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
  13. #pragma comment(linker, "/stack:200000000")
  14. #pragma GCC optimize("Ofast")
  15. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  16. #define FILE_IN "birds.inp"
  17. #define FILE_OUT "birds.out"
  18. #define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
  19. #define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  20. #define nfio cin.tie(0);cout.tie(0)
  21. #define max(x,y) (((x)>(y))?(x):(y))
  22. #define min(x,y) (((x)<(y))?(x):(y))
  23. #define ord(a,b,c) ((a>=b)and(b>=c))
  24. #define MOD (ll(1000000007))
  25. #define MAX 300001
  26. #define mag 320
  27. #define p1 first
  28. #define p2 second.first
  29. #define p3 second.second
  30. #define fi first
  31. #define se second
  32. #define pow2(x) (ll(1)<<x)
  33. #define pii pair<int,int>
  34. #define piii pair<int,pii>
  35. #define For(i,__,___) for(int i=__;i<=___;i++)
  36. #define Rep(i,__,___) for(int i=__;i>=___;i--)
  37. #define ordered_set tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update>
  38. #define endl "\n"
  39. #define bi BigInt
  40. #define pi 3.1415926535897
  41. typedef long long ll;
  42. struct node // Structure representing a node.
  43. {
  44. 	int parent,slink,trans[128];
  45. 	/*
  46. 	parent: id of node's parent. 0 if this node is the root.
  47. 	slink: id of node's direct suffix link. 1 if this node is the root.
  48. 	trans[i]: The next node's id if the next character in the automaton is i. Will be found recursively using slink
  49. 	negative: use suffix link
  50. 	positive: use trie link
  51. 	0: not set
  52. 	-1 if this node is the root and there's no trie link with this character.
  53. 	*/
  54. 	int pedge;
  55. 	/*
  56. 	pedge: character of the edge connecting parent of node to node
  57. 	*/
  58. 	vector<int> leaf;
  59. 	/*
  60. 	leaf: list of ids of strings that are suffixes of the string represented by current node. Will be found recursively using slink
  61. 	*/
  62. 	 node(int par=0 ,int edge=0) // Constructor
  63. 	{
  64. 		for (int i=0;i<128;i++) trans[i]=0; 
  65. 		parent=par;
  66. 		slink=0;
  67. 		pedge=edge;
  68. 		leaf={};
  69. 	}	
  70. };
  71. struct aho_cora // Structure representing a suffix automaton.
  72. {
  73. 	private:
  74. 		vector<node> trie; // A vector of nodes representing the trie.
  75. 		int scnt=0; // Count of strings added to the trie. Will be used to number the strings added to the trie.
  76. 		int add_node (int par, int last) 
  77. 		/*
  78. 		Add a node into the tree with parent par and edge character last.
  79. 		*/
  80. 		{
  81. 			trie.push_back(node(par,last));
  82. 			int cur=trie.size()-1;
  83.  
  84. 			return cur;
  85. 		}
  86. 		void refresh_node(int cur)
  87. 		/*
  88. 		Add the suffix links and transition table for node cur, then calls the function for its children.
  89. 		*/
  90. 		{
  91. 			if (trie[cur].parent<=1) trie[cur].slink=1; // If string represented by node has <=1 character, then it has no suffixes, so its direct suffix link is 1. 
  92. 			else  
  93. 			trie[cur].slink=abs(trie[trie[trie[cur].parent].slink].trans[trie[cur].pedge]); 
  94. 			/*
  95. 			"to find a suffix link for some vertex v, then we can go to the ancestor 
  96. 			p of the current vertex (let c be the letter of the edge from p to v), 
  97. 			then follow its suffix link, and perform from there the transition with the letter c."
  98. 			*/
  99. 			for (int i=0;i<128;i++) if (trie[cur].trans[i]<=0) trie[cur].trans[i]=-abs(trie[trie[cur].slink].trans[i]);
  100. 			/*
  101. 			For transitions not using trie links, import the transition results from the node's suffix link node.
  102. 			*/
  103. 			for (int g: trie[trie[cur].slink].leaf) trie[cur].leaf.push_back(g);
  104. 			/*
  105. 			Adds the suffix link node's leaf vector to the node's leaf vector.
  106. 			*/
  107. 			// for (int i=0;i<128;i++) if (trie[cur].trans[i]>0) refresh_node(trie[cur].trans[i]);
  108. 			/*
  109. 			Calls refresh_node() for its children.
  110. 			*/
  111. 		}
  112. 	public:
  113. 		 aho_cora() // Constructor
  114. 		{
  115. 			trie.push_back(node(0));
  116. 			trie.push_back(node(0));
  117. 			trie[1].parent=0;
  118. 			trie[1].slink=1;
  119. 			trie[1].leaf={};
  120. 			for (int i=0;i<128;i++) trie[1].trans[i]=-1;
  121. 		}
  122. 		void add_string (string s) //Adds a string to the trie.
  123. 		{
  124. 			scnt++; //Increments the string counter. This string's id is now scnt.
  125. 			int cur=1,n=s.length(); //Starts at node 1
  126. 			for (int i=0;i<n;i++)
  127. 			{
  128. 				if (trie[cur].trans[s[i]]<=0) //If there's no trie link with this character yet, create a new one (along with a new node)
  129. 				{	
  130. 				int ass=add_node(cur,s[i]);
  131. 				trie[cur].trans[s[i]]=ass;
  132. 				}
  133. 				cur=trie[cur].trans[s[i]]; //Transitions to next node via the trie link for the current character.
  134. 			}
  135. 			trie[cur].leaf.push_back(scnt); //Once we've arrived at the node for the string, add the string id to its leaf vector.
  136. 		}
  137. 		vector<pii> check_string(string s) 
  138. 		/*
  139. 			Returns all occurences of pattern strings in the given text, in the form of a vector of pairs. 
  140. 			First element is the end position of the matching pattern string (relative to the text).
  141. 			Second element is the id of the matching patten string 
  142. 			(pattern strings are numbered from 1 to n, based on when you added them) 
  143. 		*/
  144. 		{
  145. 			vector<pii> res;
  146. 			int n=s.length();
  147. 			int cur=1; // Starts at node 1
  148. 			for (int i=0;i<n;i++)
  149. 			{
  150. 				cur=abs(trie[cur].trans[s[i]]); // Transitions to next node based on the current character.
  151. 				for  (int g: trie[cur].leaf)
  152. 				{
  153. 					res.push_back({i,g}); //Adds the node's leaf array to the results array.
  154. 				}
  155. 			}
  156. 			return res;
  157. 		}
  158. 		void check_graph() // Debug
  159. 		{
  160. 			for (int i=1;i<trie.size();i++)
  161. 			{
  162. 			cout<<i<<' '<<trie[i].parent<<' '<<trie[i].slink<<' '<<endl;
  163. 			for (int j=0;j<128;j++) cout<<trie[i].trans[j]<<' ';
  164. 			cout<<endl;
  165. 			for (int g: trie[i].leaf) cout<<g<<' ';
  166. 			cout<<endl;
  167. 			}
  168. 		}
  169. 		void refresh() // Refreshes the tree; see refresh_node()
  170. 		{
  171. 			queue<int> que;
  172.       que.push(1);
  173.       set<int> done;
  174.       while (!que.empty()) {
  175.         if (!done.count(que.front())) {
  176.           done.insert(que.front());
  177.           refresh_node(que.front());
  178.           for (int i=0;i<128;i++) if (trie[que.front()].trans[i]>0) que.push(trie[que.front()].trans[i]);
  179.         }
  180.         que.pop();
  181.       }
  182. 		}
  183.  
  184. };
  185. ll n,m,k,c[501],t,t1,i,j,res;
  186. vector<ll> gt[51];
  187. int main()
  188. {
  189.     while(1)
  190.     {
  191. 		n=0;
  192. 		cin>>n;
  193. 		cin.ignore();
  194. 		aho_cora graph;
  195. 		if (!n) break;
  196. 		int len[n];
  197. 		for (i=0;i<n;i++)
  198. 		{
  199. 			string s;
  200. 			getline(cin,s);
  201. 			len[i]=s.length();
  202. 			graph.add_string(s);
  203. 		}
  204. 		    graph.refresh();
  205. 			string s;
  206. 			getline(cin,s);
  207. 			vector<int> match[100001];
  208. 			vector<pii> res=graph.check_string(s);
  209. 			for (i=0;i<res.size();i++) match[res[i].se].push_back(res[i].fi);
  210. 			for (i=0;i<n;i++)
  211. 			{
  212. 				for (int g: match[i+1]) cout<<g-len[i]+1<<' ';
  213. 				cout<<endl;
  214. 			}
  215.     }
  216. }
  217.  
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bbhJde
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!