fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <vector>
  5. #include <list>
  6. #include <map>
  7. #include <set>
  8. #include <queue>
  9. #include <stack>
  10. #include <bitset>
  11. #include <algorithm>
  12. #include <sstream>
  13. #include <iomanip>
  14. #include <cmath>
  15. #include <cstdlib>
  16. #include <cctype>
  17. #include <cstring>
  18. #include <string>
  19. #include <ctime>
  20. #include <cassert>
  21. #include <utility>
  22.  
  23. using namespace std;
  24.  
  25. #define MAXN 200050
  26.  
  27. int N;
  28. char S[MAXN];
  29. int Zaux[MAXN];
  30. int Z[MAXN];
  31. int RZ[MAXN];
  32. bool flag;
  33. long long ans;
  34.  
  35. // index idx in [a..b]
  36. inline char getCh(int a, int b, int idx) {
  37. 	return S[a + idx * (a <= b ? 1 : -1)];
  38. }
  39.  
  40. // Z for [a..b] in [c..d]
  41. void calcZ(int a, int b, int c, int d, int Z[MAXN]) {
  42. 	int sz1 = abs(b - a) + 1;
  43. 	int sz2 = abs(d - c) + 1;
  44.  
  45. 	int L = -1;
  46. 	int R = -1;
  47.  
  48. 	Zaux[0] = sz2;
  49. 	for (int i = 1; i < sz1; i++) {
  50. 		if (i > R) {
  51. 			L = R = i;
  52. 			while (R < sz2 && R - L < sz2 && getCh(c, d, R) == getCh(c, d, R - L)) {
  53. 				R++;
  54. 			}
  55. 			R--;
  56. 			Zaux[i] = R - L + 1;
  57. 		}
  58. 		else {
  59. 			int k = i - L;
  60. 			Zaux[i] = min(Zaux[k], R - i + 1);
  61. 			if (Zaux[i] == R - i + 1) {
  62. 				L = i;
  63. 				while (R < sz2 && R - L < sz2 && getCh(c, d, R) == getCh(c, d, R - L)) {
  64. 					R++;
  65. 				}
  66. 				R--;
  67. 				Zaux[i] = R - L + 1;
  68. 			}
  69. 		}
  70. 	}
  71.  
  72. 	if (a <= b) {	
  73. 		L = R = -1;
  74. 		for (int i = 0; i < sz1; i++) {
  75. 			if (i > R) {
  76. 				L = i;
  77. 				R = i;
  78. 				while (R < sz1 && R - L < sz2 && getCh(a, b, R) == getCh(c, d, R - L)) {
  79. 					R++;
  80. 				}
  81. 				R--;
  82. 				Z[i] = R - L + 1;
  83. 			}
  84. 			else {
  85. 				int k = i - L;
  86. 				Z[i] = min(Zaux[k], R - i + 1);
  87. 				if (Z[i] == R - i + 1) {
  88. 					L = i;
  89. 					while (R < sz1 && R - L < sz2 && getCh(a, b, R) == getCh(c, d, R - L)) {
  90. 						R++;
  91. 					}
  92. 					R--;
  93. 					Z[i] = R - L + 1;
  94. 				}
  95. 			}
  96. 		}
  97. 	}
  98. 	else { // a > b
  99. 		for (int i = 0; i < sz1; i++) {
  100. 			Z[i] = Zaux[sz1 - 1 - i];
  101. 		}
  102. 	}
  103. }
  104.  
  105. void go(int st, int m, int dr) {
  106. 	calcZ(st, m, m + 1, dr, Z);
  107. 	calcZ(m, st, m, st, RZ);
  108.  
  109. 	int len = m - st + 1;
  110.  
  111. //	printf("(%d, %d, %d) ->\n", st, m, dr);
  112. //	for (int i = 0; i < len; i++) { printf("%d ", Z[i]); } printf("\n");
  113. //	for (int i = 0; i < len; i++) { printf("%d ", RZ[i]); } printf("\n");
  114.  
  115. 	if (flag) {
  116. 		for (int i = 0; i < len; i++) {
  117. 			if (i + Z[i] == len) {
  118. 				ans++;
  119. 			}
  120. 		}
  121. 	}
  122.  
  123. 	for (int i = 1; i < len - 1; i++) {
  124. 		int upper = min(i + Z[i], len - 1);
  125. 		int lower = max(i + 1, len - RZ[i - 1]);
  126. 		ans += max(0, upper - lower + 1);
  127. 	}
  128. }
  129.  
  130. void solve(int st, int dr) {
  131. 	if (st == dr) {
  132. 		return;
  133. 	}
  134. 	int m = (st + dr) / 2;
  135. 	if (!flag) {
  136. 		m = (st + dr - 1) / 2;
  137. 	}
  138.  
  139. 	go(st, m, dr);
  140.  
  141. 	solve(st, m);
  142. 	solve(m + 1, dr);
  143. }
  144.  
  145. int brute() {
  146. 	string ss(S);
  147. 	int ret = 0;
  148. 	for (int i = 0; i < N; i++) {
  149. 		for (int j = 1; i + 2 * j - 1 < N; j++) {
  150. 			if (ss.substr(i, j) == ss.substr(i + j, j)) {
  151. 				ret++;
  152. 			}
  153. 		}
  154. 	}
  155. 	return ret;
  156. }
  157.  
  158. int main() {
  159. //	freopen("date.in", "r", stdin);
  160. //	freopen("date.out","w", stdout);
  161.  
  162. 	fgets(S, sizeof(S), stdin);
  163. 	N = strlen(S);
  164. 	while (!isalpha(S[N - 1])) {
  165. 		S[N - 1] = '\0';
  166. 		N--;
  167. 	}
  168.  
  169. //	cout << brute() << endl;
  170.  
  171. 	ans = 0;
  172. 	flag = true;
  173. 	solve(0, N - 1);
  174.  
  175. 	reverse(S, S + N);
  176. 	flag = false;
  177. 	solve(0, N - 1);
  178.  
  179. 	cout << ans << endl;
  180.  
  181. //	srand(time(0));
  182. //	for (int i = 0; i < 500; i++) {
  183. //		printf("%c", 'a' + rand() % 8);
  184. //	}
  185.  
  186. 	return 0;
  187. }
  188.  
Success #stdin #stdout 0s 5888KB
comments (?)
stdin
copy 
aCacaacaa
stdout
copy 
4
https://ideone.com/vC4bJT
language:
C++ (gcc 8.3)
created:
9 years 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!