fork 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 mod 1000000007
  10.  
  11. bool isSuffix (string &str, int iStart, int iEnd, int jStart)
  12. {
  13. 	for (int i = iStart, j = jStart; i <= iEnd; i++, j++)
  14. 			if (str[i] != str[j])
  15. 				return false;
  16. 	return true;
  17. }
  18.  
  19. void isPalin(string &str, int i, int j, int &count)
  20. {
  21. 	static int id = 0;
  22. 	//cout << "PA " << "id = " << id  <<  "  "  << endl;
  23. 	id++;
  24.  
  25.  
  26.  
  27. 	int start = i;
  28. 	int end = j;
  29.  
  30. 	while (i < end)
  31. 	{
  32. 		if (str[i] == str[j]) 
  33. 		{
  34. 			if (isSuffix(str, start, i,  j))
  35. 			{
  36. 				count++;
  37. 				count %= mod;
  38. 			//	cout << i << "  "  << j  << "  "  <<  count  <<  endl;
  39.  
  40. 			}
  41. 			i++, j--;
  42.  
  43. 		}
  44. 		else
  45. 		{
  46. 			break;
  47. 		}
  48. 	}
  49.  
  50. }
  51.  
  52. int main()
  53. {
  54. 	int t;
  55. 	//cin >> t;
  56. 	t = 1;
  57.  
  58. 	while (t > 0)  {
  59.  
  60. 		string str;
  61.  
  62. 		cin >> str;
  63.  
  64. 		int start_s = clock();
  65.  
  66.  
  67. 		int n = str.length();
  68.  
  69. 		//buildSuffixArray(str, str.length());
  70. 		//int n = suffixArr.size();
  71.  
  72. 		int count = 0;
  73. 		int indx = 1;
  74. 		for (int c = 0; c < n; c++)
  75. 		{
  76. 			for (int i = 1; i <= n - c; i++)
  77. 			{
  78. 				//string sub_str = str.substr(c, i);
  79. 				//cout << indx << "  "  <<  c  <<  "  "  <<  i  <<  "  "  << sub_str << endl;
  80. 				indx++;
  81.  
  82. 				int left = c;
  83. 				int right = c + i - 1;
  84.  
  85. 				isPalin(str, left, right, count);
  86. 			}
  87.  
  88. 		}
  89.  
  90. 		cout << count  <<  endl;
  91.  
  92. 		int stop_s = clock();
  93. 		float run_time = (stop_s - start_s) / double(CLOCKS_PER_SEC);
  94. 		cout << endl << "palindromic borders  \t\tExecution time = " << run_time << " seconds" << endl;
  95.  
  96. 		t--;
  97. 	}
  98.  
  99. 	return 0;
  100. }
  101.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
ababa
stdout
copy 
5

palindromic borders  		Execution time = 1e-05 seconds
https://ideone.com/PUGTSX
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!