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 MX = 4e5 + 5; 
  12. const int N = 1e5 + 5; 
  13.  
  14. struct Node {
  15. 	int nxt[26]; 
  16. 	int cnt = 0;  
  17. 	bool mark = false; 
  18.  
  19. 	Node() {
  20. 		memset(nxt, -1, sizeof nxt); 
  21. 	}
  22. }; 
  23.  
  24. int sz; 
  25. Node trie[MX]; 
  26.  
  27. void addString(const string& s) {
  28. 	int v = 0;  
  29. 	for (char ch : s) {
  30. 		int c = ch - 'a'; 
  31. 		if (trie[v].nxt[c] == -1) {
  32. 			trie[v].nxt[c] = ++sz; 
  33. 		}
  34. 		v = trie[v].nxt[c];
  35. 		++trie[v].cnt;
  36. 	}
  37. 	trie[v].mark = true; 
  38. }
  39.  
  40. int n, q;  
  41. string s[N]; 
  42. int add[N][26][26]; // add[i][c1][c2] = Giả sử c1 < c2, thì cặp (c1, c2) đóng góp vào vị trí sau khi sort của xâu s[i] bao nhiêu
  43. int cnt_pref[N]; // cnt_pref[i] = Số xâu là prefix của xâu s[i]
  44.  
  45. void precompute() { // O(n + MX * 26)
  46. 	for (int i = 1; i <= n; i++) {
  47. 		int v = 0;  
  48. 		for (char ch : s[i]) {
  49. 			int c = ch - 'a';  
  50. 			for (int c1 = 0; c1 <= 25; c1++) {
  51. 				if (c1 == c) continue; 
  52. 				int nxt_v = trie[v].nxt[c1]; 
  53. 				if (nxt_v == -1) continue;   
  54. 				add[i][c1][c] += trie[nxt_v].cnt;   
  55. 			}
  56. 			v = trie[v].nxt[c];
  57. 			cnt_pref[i] += trie[v].mark;  
  58. 		}
  59. 	}
  60. }
  61.  
  62. // Vị trí của xâu s[i] sau khi sort, nếu ta tuân theo thứ tự các chữ cái của p
  63. int findIndex(int i, const string& p) { // O(26^2)
  64. 	int ans = 0;
  65. 	for (int j = 0; j + 1 <= 25; j++) {
  66. 		int c1 = p[j] - 'a';
  67. 		for (int k = j + 1; k <= 25; k++) {
  68. 			int c2 = p[k] - 'a';  
  69. 			ans += add[i][c1][c2]; 
  70. 		}
  71. 	}
  72.  
  73. 	ans += cnt_pref[i]; 
  74.  
  75. 	return ans; 
  76. }
  77.  
  78. int main() {
  79. 	ios::sync_with_stdio(false); 
  80. 	cin.tie(nullptr); 	
  81. 	cin >> n; 
  82. 	for (int i = 1; i <= n; i++) {
  83. 		cin >> s[i]; 
  84. 		addString(s[i]); 
  85. 	}
  86.  
  87. 	precompute();   
  88.  
  89. 	cin >> q; 
  90.  
  91. 	while (q--) {
  92. 		int i; string p;  
  93. 		cin >> i >> p;  
  94. 		cout << findIndex(i, p) << '\n'; 	
  95. 	}
  96. }
Success #stdin #stdout 0.01s 51688KB
comments (?)
stdin
copy 
5
aa
abbaa
abbba
aaab
aaaaaba
5
1 abcdefghijklmnopqrstuvwxyz
2 bacdefghijklmnopqrstuvwxyz
3 abcdefghijklmnopqrstuvwxyz
4 bacdefghijklmnopqrstuvwxyz
5 abcdefghijklmnopqrstuvwxyz
stdout
copy 
1
2
5
4
2
https://ideone.com/A6ACKw
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!