fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define all(x) begin(x), end(x)
  6. #define int int64_t
  7.  
  8. const int maxn = 1001;
  9.  
  10. int pre[maxn][maxn], suf[maxn][maxn], is_pal[maxn][maxn], lcp[maxn][maxn];
  11.  
  12. signed main() {
  13. 	//freopen("input.txt", "r", stdin);
  14. 	//freopen("output.txt", "w", stdout);
  15. 	ios::sync_with_stdio(0);
  16. 	cin.tie(0);
  17. 	string s;
  18. 	cin >> s;
  19. 	int n = s.size();
  20. 	for(int i = 0; i < n; i++) {
  21. 		is_pal[i][i] = 1;
  22. 		pre[i][i] = suf[i][i] = 2;
  23. 		if(i > 0) {
  24. 			is_pal[i][i - 1] = pre[i][i - 1] = suf[i][i - 1] = 1;
  25. 		}
  26. 	}
  27. 	for(int i = 0; i < n; i++) {
  28. 		for(int j = i + 1; j < n; j++) {
  29. 			lcp[i][j] = (s[i] == s[j]) * (1 + (i > 0 && j + 1 < n ? lcp[i - 1][j + 1] : 0));
  30. 		}
  31. 	}
  32. 	for(int len = 1; len < n; len++) {
  33. 		for(int i = 0; i + len < n; i++) {
  34. 			is_pal[i][i + len] = (s[i] == s[i + len]) * is_pal[i + 1][i + len - 1];
  35. 			pre[i][i + len] = is_pal[i][i + len] + pre[i][i + len - 1];
  36. 			suf[i][i + len] = is_pal[i][i + len] + suf[i + 1][i + len];
  37. 		}
  38. 	}
  39. 	int ans = 0;
  40. 	for(int i = 0; i < n; i++) {
  41. 		for(int j = i + 1; j < n; j++) {
  42. 			ans += lcp[i][j] * (pre[i + 1][j - 1] + suf[i + 1][j - 1] - 1);
  43. 		}
  44. 	}
  45. 	cout << ans << endl;
  46. 	return 0;
  47. }
  48.  
Success #stdin #stdout 0s 46552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/vV3BUj
language:
C++14 (gcc 8.3)
created:
6 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!