fork(1) download 
  1. // algoritmus Aho-Corasick
  2. // cas O(velkost vstupu)=O(N+M)
  3. #include <iostream>
  4. #include <vector>
  5. #include <queue>
  6. using namespace std;
  7.  
  8. struct node {bool KONCI; int syn[5]; int mensi,par,pis;};
  9.  
  10. int main() {
  11. 	int N,M;
  12. 	string s;
  13. 	vector<node> trie; // pismenkovy strom
  14. 	node n;
  15. 	for(int i =0; i < 5; i++) n.syn[i] =-1;
  16. 	n.KONCI =false;
  17. 	n.mensi =n.par =0;
  18. 	n.pis ='0';
  19. 	trie.push_back(n);
  20.  
  21. 	cin >> N;
  22. 	for(int k =0; k < N; k++) {
  23. 		cin >> s;
  24. 		int akt =0; // aktualny vrchol v ktorom sme
  25. 		for(unsigned int i =0; i < s.length(); i++) {
  26. 			if(trie[akt].syn[s[i]-'1'] == -1) {
  27. 				trie[akt].syn[s[i]-'1'] =trie.size();
  28. 				n.par =akt;
  29. 				n.pis =s[i]-'1';
  30. 				trie.push_back(n);}
  31. 			akt =trie[akt].syn[s[i]-'1'];}
  32. 		trie[akt].KONCI =true;}
  33.  
  34. 	// prejdeme vrcholy trie podla rastucej hlbky, hladame prve mensie vrcholy
  35. 	queue<int> d,q;
  36. 	q.push(0);
  37. 	while(!q.empty()) {
  38. 		for(int i =0; i < 5; i++) if(trie[q.front()].syn[i] != -1) q.push(trie[q.front()].syn[i]);
  39. 		d.push(q.front());
  40. 		q.pop();}
  41. 	while(!d.empty()) {
  42. 		// najdeme prvy mensi vrchol
  43. 		trie[d.front()].mensi =trie[trie[d.front()].par].mensi;
  44. 		while(trie[d.front()].mensi != 0 && trie[trie[d.front()].mensi].syn[trie[d.front()].pis] == -1) 
  45. 			trie[d.front()].mensi =trie[trie[d.front()].mensi].mensi;
  46. 		if(trie[trie[d.front()].mensi].syn[trie[d.front()].pis] != -1) 
  47. 			trie[d.front()].mensi =trie[trie[d.front()].mensi].syn[trie[d.front()].pis];
  48. 		if(d.front() == trie[d.front()].mensi) trie[d.front()].mensi =0;
  49. 		d.pop();}
  50.  
  51.  
  52. 	cin >> M;
  53. 	bool zac =true;
  54. 	for(int k =0; k < M; k++) {
  55. 		cin >> s;
  56. 		int akt =0;
  57. 		bool smie =true;
  58. 		for(unsigned int i =0; i < s.length(); i++) {
  59. 			// zmen prefix
  60. 			while(akt != 0 && trie[akt].syn[s[i]-'1'] == -1) akt =trie[akt].mensi;
  61. 			if(trie[akt].syn[s[i]-'1'] != -1) akt =trie[akt].syn[s[i]-'1'];
  62. 			// ak tu slovo konci
  63. 			if(trie[akt].KONCI) {smie =false; break;}}
  64. 		if(!smie) {
  65. 			if(zac) zac =false;
  66. 			else cout << " ";
  67. 			cout << k+1;}}
  68. 	cout << endl;
  69. 	return 0;}
Success #stdin #stdout 0s 2972KB
comments (?)
stdin 
2
152
3
4
33125
421425
3
5555521
stdout 
1 3
https://ideone.com/JaLLt
language:
C++14 (gcc 8.3)
created:
14 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!