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 p = 31; 
  12. const int MOD = 1e9 + 9277; 
  13. const int MX = 1e6 + 5; 
  14. const int N = 1e6 + 5; 
  15.  
  16. int n;  
  17. string s[N]; 
  18. int sz[N]; 
  19.  
  20. int p_pow[MX], inv_p_pow[MX]; 
  21. vector<int> h[N], rev_h[N]; 
  22.  
  23. int binpow(int a, int b) {
  24. 	int ans = 1; 
  25. 	for (; b > 0; b >>= 1) {
  26. 		if (b & 1) ans = 1ll * ans * a % MOD;  
  27. 		a = 1ll * a * a % MOD; 
  28. 	}
  29. 	return ans;
  30. }
  31.  
  32. void precompute() {
  33. 	p_pow[0] = 1; 
  34. 	for (int i = 1; i < MX; i++) p_pow[i] = 1ll * p_pow[i - 1] * p % MOD; 
  35.  
  36. 	inv_p_pow[MX - 1] = binpow(p_pow[MX - 1], MOD - 2); 
  37. 	for (int i = MX - 2; i >= 0; i--) inv_p_pow[i] = 1ll * inv_p_pow[i + 1] * p % MOD; 
  38. }
  39.  
  40. void computeHash(int i, const string& s, int sz) {
  41. 	h[i] = rev_h[i] = vector<int>(sz + 1); 
  42. 	h[i][0] = rev_h[i][0] = 0;  
  43. 	for (int j = 1; j <= sz; j++) {
  44. 		h[i][j] = (1ll * h[i][j - 1] * p + (s[j] - 'a' + 1)) % MOD; 
  45. 		rev_h[i][j] = (rev_h[i][j - 1] + 1ll * p_pow[j - 1] * (s[j] - 'a' + 1) % MOD) % MOD; 
  46. 	}
  47. }	
  48.  
  49. int getHash(int i, int l, int r) {
  50. 	return (h[i][r] - 1ll * h[i][l - 1] * p_pow[r - l + 1] % MOD + MOD) % MOD; 
  51. }
  52.  
  53. int getRevHash(int i, int l, int r) {
  54. 	return 1ll * (rev_h[i][r] - rev_h[i][l - 1] + MOD) % MOD * inv_p_pow[l - 1] % MOD; 
  55. }
  56.  
  57. bool isPalin(int i, int l, int r) {
  58. 	return (getHash(i, l, r) == getRevHash(i, l, r));
  59. }
  60.  
  61. struct Node {
  62. 	int nxt[26]; 
  63. 	int mark = 0;   
  64.  
  65. 	Node() {
  66. 		memset(nxt, -1, sizeof nxt); 
  67. 	}
  68. }; 
  69.  
  70. struct PrefixTrie {
  71. 	vector<Node> trie;  
  72.  
  73. 	PrefixTrie() {
  74. 		trie = vector<Node>(1);
  75. 	}
  76.  
  77. 	void addString(const string& s, int sz) {
  78. 		int v = 0;  
  79. 		for (int i = 1; i <= sz; i++) {
  80. 			int c = s[i] - 'a'; 
  81. 			if (trie[v].nxt[c] == -1) {
  82. 				trie[v].nxt[c] = trie.size(); 
  83. 				trie.push_back(Node()); 
  84. 			}
  85. 			v = trie[v].nxt[c]; 
  86. 		}
  87. 		trie[v].mark++; 
  88. 	}
  89. }; 
  90.  
  91. PrefixTrie PrefTrie; 
  92.  
  93. struct SuffixTrie {
  94. 	vector<Node> trie;  
  95.  
  96. 	SuffixTrie() {
  97. 		trie = vector<Node>(1);
  98. 	}
  99.  
  100. 	void addString(const string& s, int sz) {
  101. 		int v = 0;  
  102. 		for (int i = sz; i >= 1; i--) {
  103. 			int c = s[i] - 'a'; 
  104. 			if (trie[v].nxt[c] == -1) {
  105. 				trie[v].nxt[c] = trie.size(); 
  106. 				trie.push_back(Node()); 
  107. 			}
  108. 			v = trie[v].nxt[c]; 
  109. 		}
  110. 		trie[v].mark++; 
  111. 	}
  112. }; 
  113.  
  114. SuffixTrie SufTrie;  
  115.  
  116. int main() {
  117. 	ios::sync_with_stdio(false); 
  118. 	cin.tie(nullptr); 	
  119. 	cin >> n; 
  120.  
  121. 	precompute();  
  122.  
  123. 	for (int i = 1; i <= n; i++) {
  124. 		cin >> sz[i]; 
  125. 		cin >> s[i]; 
  126. 		s[i] = ' ' + s[i]; 
  127. 		computeHash(i, s[i], sz[i]); 
  128. 		PrefTrie.addString(s[i], sz[i]); 
  129. 		SufTrie.addString(s[i], sz[i]); 
  130. 	}
  131.  
  132. 	// sz[i] >= sz[j]
  133. 	ll ans = 0;  
  134. 	for (int i = 1; i <= n; i++) {
  135. 		int v = 0;   
  136. 		for (int k = 1; k <= sz[i]; k++) {
  137. 			int c = s[i][k] - 'a'; 
  138. 			v = SufTrie.trie[v].nxt[c];  
  139. 			if (v == -1) break; 
  140. 			ans += isPalin(i, k + 1, sz[i]) * SufTrie.trie[v].mark; 
  141. 		}
  142. 	}
  143.  
  144. 	// sz[i] < sz[j]
  145. 	for (int j = 1; j <= n; j++) {
  146. 		int v = 0;  
  147. 		for (int k = sz[j]; k >= 2; k--) {
  148. 			int c = s[j][k] - 'a'; 
  149. 			v = PrefTrie.trie[v].nxt[c]; 
  150. 			if (v == -1) break; 
  151. 			ans += isPalin(j, 1, k - 1) * PrefTrie.trie[v].mark; 
  152. 		}
  153. 	}
  154.  
  155. 	cout << ans << '\n';
  156. }
Success #stdin #stdout 0.03s 91364KB
comments (?)
stdin
copy 
3
1 a
2 ab
2 ba
stdout
copy 
5
https://ideone.com/KdWicn
language:
C++14 (gcc 8.3)
created:
333 days 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!