fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. Para frecuencias
  6. template<int E = 26> // E = Alfabeto
  7. struct AhoCorasick {
  8. 	int nodes;
  9. 	vector<int> suf;
  10. 	vector<int> freq;
  11. 	vector<int> by_level;
  12. 	vector<bool> terminal;
  13. 	vector<array<int, E>> go;
  14.  
  15. 	AhoCorasick() {
  16. 		add_node();
  17. 		nodes = 1;
  18. 	}
  19.  
  20. 	void add_node() {
  21. 		terminal.emplace_back();
  22. 		suf.emplace_back();
  23. 		go.emplace_back();
  24. 		freq.emplace_back();
  25. 	}
  26.  
  27. 	void insert(string &s) {
  28. 		int pos = 0;
  29. 		for (char ch : s) {
  30. 			int c = ch - 'a';
  31. 			if (go[pos][c] == 0) {
  32. 				go[pos][c] = nodes++;
  33. 				add_node();
  34. 			}
  35. 			pos = go[pos][c];
  36. 		}
  37. 		terminal[pos] = true;
  38. 	}
  39.  
  40. 	void build() {
  41. 		queue<int> Q;
  42. 		Q.emplace(0);
  43. 		while (not Q.empty()) {
  44. 			int u = Q.front(); Q.pop();
  45. 			by_level.emplace_back(u);
  46. 			for (int c = 0; c < E; ++c) {
  47. 				if (go[u][c]) {
  48. 					int v = go[u][c];
  49. 					Q.emplace(v);
  50. 					suf[v] = u == 0 ? 0 : go[suf[u]][c];
  51. 				}
  52. 				else {
  53. 					go[u][c] = u == 0 ? 0 : go[suf[u]][c];
  54. 				}
  55. 			}
  56. 		}
  57. 	}
  58. };*/
  59.  
  60. // Para existencia
  61. template<int E = 26> // E = Alfabeto
  62. struct AhoCorasick {
  63. 	int nodes;
  64. 	vector<int> suf;
  65. 	vector<int> super;
  66. 	vector<bool> terminal;
  67. 	vector<array<int, E>> go;
  68.  
  69. 	AhoCorasick() {
  70. 		add_node();
  71. 		nodes = 1;
  72. 	}
  73.  
  74. 	void add_node() {
  75. 		terminal.emplace_back();
  76. 		suf.emplace_back();
  77. 		go.emplace_back();
  78. 		super.emplace_back();
  79. 	}
  80.  
  81. 	void insert(string &s) {
  82. 		int pos = 0;
  83. 		for (char ch : s) {
  84. 			int c = ch - 'a';
  85. 			if (go[pos][c] == 0) {
  86. 				go[pos][c] = nodes++;
  87. 				add_node();
  88. 			}
  89. 			pos = go[pos][c];
  90. 		}
  91. 		terminal[pos] = true;
  92. 	}
  93.  
  94. 	void build() {
  95. 		queue<int> Q;
  96. 		Q.emplace(0);
  97. 		while (not Q.empty()) {
  98. 			int u = Q.front(); Q.pop();
  99. 			super[u] = (suf[u] == 0 or terminal[suf[u]] ? suf[u] : super[suf[u]]);
  100. 			for (int c = 0; c < E; ++c) {
  101. 				if (go[u][c]) {
  102. 					int v = go[u][c];
  103. 					Q.emplace(v);
  104. 					suf[v] = u == 0 ? 0 : go[suf[u]][c];
  105. 				}
  106. 				else {
  107. 					go[u][c] = u == 0 ? 0 : go[suf[u]][c];
  108. 				}
  109. 			}
  110. 		}
  111. 	}
  112. };
  113.  
  114. template<int E = 26>
  115. void mark(int u, AhoCorasick<E> &AC) {
  116. 	if (u == 0) return;
  117. 	mark(AC.super[u], AC);
  118. 	if (AC.terminal[u]) {
  119. 		cout << "El nodo " << u << " ocurre como subcadena" << endl;
  120. 		AC.terminal[u] = false;
  121. 	}
  122. 	AC.super[u] = 0;
  123. }
  124.  
  125. int main() {
  126. 	cin.tie(0) -> sync_with_stdio(false);
  127. 	AhoCorasick<26> Solver;
  128. 	vector<string> S = {"arco", "co", "barco", "oro", "toro"};
  129. 	for (string s : S) {
  130. 		Solver.insert(s);
  131. 	}
  132. 	Solver.build();
  133. 	const string T = "coroparcotoro";
  134. 	int p = 0;
  135. 	for (char ch : T) {
  136. 		int c = ch - 'a';
  137. 		p = Solver.go[p][c];
  138. 		mark(p, Solver);
  139. 	}
  140. 	/*
  141. 	for (int i = (int)Solver.by_level.size() - 1; i > 0; --i) {
  142. 		int x = Solver.by_level[i];
  143. 		Solver.freq[Solver.suf[x]] += Solver.freq[x];
  144. 	}
  145. 	for (int i = 0; i < Solver.nodes; ++i) {
  146. 		cout << "El nodo " << i << " ocurre " << Solver.freq[i] << " veces" << endl;
  147. 	}*/
  148. 	return 0;
  149. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
El nodo 6 ocurre como subcadena
El nodo 14 ocurre como subcadena
El nodo 4 ocurre como subcadena
El nodo 18 ocurre como subcadena
https://ideone.com/0jiXeU
language:
C++14 (gcc 8.3)
created:
3 days 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!