fork(4) download
copy 
  1. // C++ program for building LCP array for given text
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <string>
  5. #include <time.h>
  6.  
  7. using namespace std;
  8.  
  9. #define MAX 100000
  10. #define mod 1000000007
  11.  
  12. struct suffix
  13. {
  14. 	int index;
  15. 	int rank[2];
  16. };
  17.  
  18. int cmp(struct suffix a, struct suffix b)
  19. {
  20. 	return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):
  21. 		(a.rank[0] < b.rank[0] ?1: 0);
  22. }
  23.  
  24. vector<int>suffixArr;
  25.  
  26. void buildSuffixArray(string txt, int n)
  27. {
  28. 	struct suffix suffixes[n];
  29.  
  30. 	for (int i = 0; i < n; i++)
  31. 	{
  32. 		suffixes[i].index = i;
  33. 		suffixes[i].rank[0] = txt[i] - 'a';
  34. 		suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1;
  35. 	}
  36.  
  37. 	sort(suffixes, suffixes+n, cmp);
  38.  
  39. 	int ind[n];
  40.  
  41. 	for (int k = 4; k < 2*n; k = k*2)
  42. 	{
  43. 		int rank = 0;
  44. 		int prev_rank = suffixes[0].rank[0];
  45. 		suffixes[0].rank[0] = rank;
  46. 		ind[suffixes[0].index] = 0;
  47.  
  48. 		for (int i = 1; i < n; i++)
  49. 		{
  50. 			if (suffixes[i].rank[0] == prev_rank &&
  51. 					suffixes[i].rank[1] == suffixes[i-1].rank[1])
  52. 			{
  53. 				prev_rank = suffixes[i].rank[0];
  54. 				suffixes[i].rank[0] = rank;
  55. 			}
  56. 			else
  57. 			{
  58. 				prev_rank = suffixes[i].rank[0];
  59. 				suffixes[i].rank[0] = ++rank;
  60. 			}
  61. 			ind[suffixes[i].index] = i;
  62. 		}
  63.  
  64. 		for (int i = 0; i < n; i++)
  65. 		{
  66. 			int nextindex = suffixes[i].index + k/2;
  67. 			suffixes[i].rank[1] = (nextindex < n)?
  68. 								suffixes[ind[nextindex]].rank[0]: -1;
  69. 		}
  70.  
  71. 		sort(suffixes, suffixes+n, cmp);
  72. 	}
  73.  
  74. 	for (int i = 0; i < n; i++)
  75. 		suffixArr.push_back(suffixes[i].index);
  76.  
  77. }
  78.  
  79. bool isSuffix (string &str, int iStart, int iEnd, int jStart)
  80. {
  81. 	for (int i = iStart, j = jStart; i <= iEnd; i++, j++)
  82. 			if (str[i] != str[j])
  83. 				return false;
  84. 	return true;
  85. }
  86.  
  87. void isPalin(string &str, int i, int j, int &count)
  88. {
  89. 	int start = i;
  90. 	int end = j;
  91.  
  92. 	while (i < end)
  93. 	{
  94. 		if (str[i] == str[j]) 
  95. 		{
  96. 			if (isSuffix(str, start, i,  j))
  97. 			{
  98. 				count++;
  99. 				count %= mod;
  100. 			}
  101. 			i++, j--;
  102.  
  103. 		}
  104. 		else
  105. 		{
  106. 			break;
  107. 		}
  108. 	}
  109.  
  110. }
  111.  
  112. int main()
  113. {
  114. 	int t;
  115. 	//cin >> t;
  116. 	t = 1;
  117.  
  118. 	while (t > 0)  {
  119.  
  120. 		string str;
  121.  
  122. 		cin >> str;
  123.  
  124. 		int start_s = clock();
  125.  
  126. 		buildSuffixArray(str, str.length());
  127. 		int n = suffixArr.size();
  128.  
  129. 		int count = 0;
  130.  
  131. 		for(int i = 0;i < n;i++)  {
  132.  
  133. 			int begin_suffix = suffixArr[i];
  134. 			int end_suffix = n - suffixArr[i];
  135.  
  136. 			for (int j = 1; j <= end_suffix; j++)  {
  137.  
  138. 				if (j >= 2)  {
  139. 					int left = begin_suffix;
  140. 					int right = begin_suffix + j - 1;
  141.  
  142. 					isPalin(str, left, right, count);
  143. 				}
  144. 			}
  145. 		}
  146.  
  147. 		cout << count  <<  endl;
  148.  
  149. 		int stop_s = clock();
  150. 		float run_time = (stop_s - start_s) / double(CLOCKS_PER_SEC);
  151. 		cout << endl << "palindromic borders  \t\tExecution time = " << run_time << " seconds" << endl;
  152.  
  153. 		t--;
  154. 	}
  155.  
  156. 	return 0;
  157. }
  158.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
ababa
stdout
copy 
5

palindromic borders  		Execution time = 1.4e-05 seconds
https://ideone.com/5ca8Af
language:
C++14 (gcc 8.3)
created:
7 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!