fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 25e4 + 5; 
  12. const int MX = 25e4 + 5; 
  13.  
  14. template<typename T>
  15. void maximize(T& a, const T& b) {
  16. 	if (a < b) a = b;  
  17. }
  18.  
  19. struct Node {
  20. 	int nxt[26]; 
  21. 	bool mark = false; 
  22.  
  23. 	Node() {
  24. 		memset(nxt, -1, sizeof nxt); 
  25. 	}
  26. }; 
  27.  
  28. int sz; 
  29. Node trie[MX]; 
  30.  
  31. void addString(const string& s) {
  32. 	int v = 0; 
  33. 	for (char ch : s) {
  34. 		int c = ch - 'a'; 
  35. 		if (trie[v].nxt[c] == -1) {
  36. 			trie[v].nxt[c] = ++sz; 
  37. 		}
  38. 		v = trie[v].nxt[c]; 
  39. 	}
  40. 	trie[v].mark = true; 
  41. }
  42.  
  43. // Đếm số xâu có trên đường đi từ gốc cho đến đỉnh v tương ứng với xâu s
  44. int getCount(const string& s) {
  45. 	int v = 0, ans = 0;  
  46. 	for (char ch : s) {
  47. 		int c = ch - 'a';  
  48. 		v = trie[v].nxt[c]; 
  49. 		ans += trie[v].mark;
  50. 	}
  51. 	return ans; 
  52. }
  53.  
  54. int n; 
  55. string s[N]; 
  56.  
  57. int main() {
  58. 	ios::sync_with_stdio(false); 
  59. 	cin.tie(nullptr); 	
  60. 	cin >> n; 
  61. 	for (int i = 1; i <= n; i++) cin >> s[i]; 
  62.  
  63. 	for (int i = 1; i <= n; i++) addString(s[i]); 
  64.  
  65. 	// Tìm đường đi từ gốc đi qua nhiều xâu nhất
  66. 	int ans = 0;  
  67. 	for (int i = 1; i <= n; i++) {
  68. 		maximize(ans, getCount(s[i])); 
  69. 	}
  70.  
  71. 	cout << ans << '\n'; 
  72. }
Success #stdin #stdout 0.02s 37820KB
comments (?)
stdin
copy 
3
a
ab
abc
stdout
copy 
3
https://ideone.com/ed2E0k
language:
C++14 (gcc 8.3)
created:
1 year 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!