fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int maxn = 300300;
  4. int trie[maxn][3], nd = 1;
  5. char str[44];
  6. int value[maxn], stp[maxn];
  7. int dp[44][44];
  8. int ok(int l, int r){
  9. 	if(l == r) return 1;
  10. 	if(l + 1 == r && str[l] == str[r]) return 1;
  11. 	if(l + 1 == r) return 0;
  12. 	if(dp[l][r] != -1) return dp[l][r];
  13. 	int v = ok(l + 1, r - 1);
  14. 	if(v == 0) return dp[l][r] = 0;
  15. 	if(str[l] == str[r]) return dp[l][r] = 1;
  16. 	return dp[l][r] = 0;
  17. }
  18. int count(){
  19. 	memset(dp, -1, sizeof(dp));
  20. 	int len = strlen(str);
  21. 	int ans = 0;
  22. 	for(int e = 0; e < len; e++)
  23. 		for(int f = e; f < len; f++)
  24. 			ans += ok(e, f);
  25. 	return ans;
  26. }
  27. //Tested
  28. template<typename T, bool fastQuery = true> class sparse_table{
  29. private:
  30.     vector<vector<T> > table;
  31.     int size, lg;
  32.     void build(){
  33.         for(int bit = 1; bit < lg; bit++)
  34.             for(int ptr = 0; ptr + (1<<bit) <= size; ptr++)
  35.                 table[bit][ptr] = table[bit-1][ptr] + table[bit-1][ptr + (1<<(bit-1))];
  36.     }
  37. public:
  38.     sparse_table(int size){
  39.         assert(size > 0);
  40.         this->size = size;
  41.         lg = log2(size) + 2;
  42.         table.assign(lg, vector<T>(size));
  43.     }
  44.     sparse_table(vector<T> & initial){
  45.         *this = sparse_table(initial.size());
  46.         for(int e = 0; e < size; e++)
  47.             table[0][e] = initial[e];
  48.         build();
  49.     }
  50.     T get(int from, int to){
  51.         assert(from <= to);
  52.         T ans = T();
  53.         if(fastQuery){
  54.             int nLG = __builtin_clz(1) - __builtin_clz(to - from + 1);
  55.             ans = table[nLG][from] + table[nLG][to - (1<<nLG) + 1];
  56.         } else {
  57.             for(int e = lg-1; e >= 0; e--)
  58.                 if((to + 1 - from)&(1<<e)){
  59.                     ans = ans + table[e][from];
  60.                     from += 1<<e;
  61.                 }
  62.         }
  63.         return ans;
  64.     }
  65. };
  66. struct to_rm{
  67. 	int ind, v;
  68. 	to_rm(){
  69.  
  70. 	}
  71. 	to_rm(int a, int b){
  72. 		ind = a;
  73. 		v = b;
  74. 	}
  75. 	to_rm operator + (to_rm other){
  76. 		if(v < other.v) return other;
  77. 		if(v > other.v) return * this;
  78. 		if(ind < other.ind) return * this;
  79. 		return other;
  80. 	}
  81. };
  82. int main(){
  83. 	int cs;
  84. 	scanf("%d", &cs);
  85. 	while(cs--){
  86. 		int n, q;
  87. 		scanf("%d %d", &n, &q);
  88. 		nd = 1;
  89. 		for(int e = 0; e < 3; e++) trie[0][e] = 0;
  90. 		for(int e = 0; e < n; e++){
  91. 			scanf("%s", str);
  92. 			value[e] = count();
  93. 			int cur = 0;
  94. 			for(int f = 0; str[f]; f++){
  95. 				int & v = trie[cur][str[f]-'a'];
  96. 				if(v == 0){
  97. 					for(int g = 0; g < 3; g++) trie[nd][g] = 0;
  98. 					v = nd++;
  99. 				}
  100. 				cur = v;
  101. 			}
  102. 			// cout <<e  << " " << value[e] << endl;
  103. 			stp[cur] = e;
  104. 		}
  105. 		vector<to_rm> lol;
  106. 		for(int e = 0; e < n;e++) lol.push_back(to_rm(e, value[e]));
  107. 		sparse_table<to_rm> sss(lol);
  108. 		for(int e = 0; e < q; e++){
  109. 			char s1[44], s2[44];
  110. 			int l, r;
  111. 			scanf("%s %s", s1, s2);
  112. 			int cur = 0;
  113. 			for(int f = 0; s1[f]; f++){
  114. 				cur = trie[cur][s1[f]-'a'];
  115. 			}
  116. 			l = stp[cur];
  117. 			cur = 0;
  118. 			for(int f = 0; s2[f]; f++){
  119. 				cur = trie[cur][s2[f]-'a'];
  120. 			}
  121. 			r = stp[cur];
  122. 			if(l > r) swap(l, r);
  123. 			// cout << l << " " << r << endl;
  124. 			printf("%d\n", sss.get(l, r).ind + 1);
  125. 		}
  126. 	}
  127. 	return 0;
  128. }
Success #stdin #stdout 0s 8760KB
comments (?)
stdin
copy 
1
5 5
aaaaa
abaabc
cbbaca
abccba
abca
aaaaa abca
cbbaca abccba
abaabc abccba
abccba abca
abaabc abccba
stdout
copy 
1
4
2
4
2
https://ideone.com/U1GmWp
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 years 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!