fork download
copy 
  1. // Find all palindrome substrings in a given string
  2. // (C)2012 mgr Jerzy Wałaszek
  3. //-----------------------------
  4.  
  5. #include <iostream>
  6. #include <string>
  7. #include <cstdlib>
  8. #include <time.h>
  9. #include <vector>
  10. #include <algorithm>
  11. //#include <string>
  12. //#include <time.h>
  13.  
  14. using namespace std;
  15.  
  16. #define MAX 100000
  17. #define mod 1000000007
  18.  
  19. struct suffix
  20. {
  21. 	int index;
  22. 	int rank[2];
  23. };
  24.  
  25. int cmp(struct suffix a, struct suffix b)
  26. {
  27. 	return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):
  28. 		(a.rank[0] < b.rank[0] ?1: 0);
  29. }
  30.  
  31. vector<int>suffixArr;
  32.  
  33. void buildSuffixArray(string txt, int n)
  34. {
  35. 	struct suffix suffixes[n];
  36.  
  37. 	for (int i = 0; i < n; i++)
  38. 	{
  39. 		suffixes[i].index = i;
  40. 		suffixes[i].rank[0] = txt[i] - 'a';
  41. 		suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1;
  42. 	}
  43.  
  44. 	sort(suffixes, suffixes+n, cmp);
  45.  
  46. 	int ind[n];
  47.  
  48. 	for (int k = 4; k < 2*n; k = k*2)
  49. 	{
  50. 		int rank = 0;
  51. 		int prev_rank = suffixes[0].rank[0];
  52. 		suffixes[0].rank[0] = rank;
  53. 		ind[suffixes[0].index] = 0;
  54.  
  55. 		for (int i = 1; i < n; i++)
  56. 		{
  57. 			if (suffixes[i].rank[0] == prev_rank &&
  58. 					suffixes[i].rank[1] == suffixes[i-1].rank[1])
  59. 			{
  60. 				prev_rank = suffixes[i].rank[0];
  61. 				suffixes[i].rank[0] = rank;
  62. 			}
  63. 			else
  64. 			{
  65. 				prev_rank = suffixes[i].rank[0];
  66. 				suffixes[i].rank[0] = ++rank;
  67. 			}
  68. 			ind[suffixes[i].index] = i;
  69. 		}
  70.  
  71. 		for (int i = 0; i < n; i++)
  72. 		{
  73. 			int nextindex = suffixes[i].index + k/2;
  74. 			suffixes[i].rank[1] = (nextindex < n)?
  75. 								suffixes[ind[nextindex]].rank[0]: -1;
  76. 		}
  77.  
  78. 		sort(suffixes, suffixes+n, cmp);
  79. 	}
  80.  
  81. 	for (int i = 0; i < n; i++)
  82. 		suffixArr.push_back(suffixes[i].index);
  83.  
  84. }
  85.  
  86. vector<pair<int,long long>> palins[MAX+5];
  87.  
  88. // Checks for proper border
  89. bool isSuffix (int jStart, pair<int,size_t> it_i)
  90. {
  91. 	for (auto& it_j : palins[jStart])
  92. 	{
  93. 		if((int)it_i.second == (int)it_j.second )
  94. 			return true;
  95. 	}
  96.  
  97. 	return false;
  98. }
  99.  
  100. // Checks for palindromes and then for proper borders
  101. int isPalin(string &str, int i, int j)
  102. {
  103.  
  104. 	int count = 0;
  105.  
  106. 	if (str[i] == str[j])
  107. 	{
  108. 		count++;
  109. 		count %= mod;
  110. 	}
  111. 	for (auto& it : palins[i])
  112. 	{
  113. 		if ( j - i > it.first && str[i] == str[j])
  114. 		{
  115. 			if (isSuffix( j - it.first, it ))
  116. 			{
  117. 				count++;
  118. 				count %= mod;
  119. 			}
  120. 		}
  121. 	}
  122. 	return count;
  123. }
  124.  
  125.  
  126. //  Finds all palindromes for the string
  127. void get_palins(string &s)
  128. {
  129. 	 int N = s.length();
  130. 	 int i, j, k,   // iterators
  131. 	 rp,        // length of 'palindrome radius'
  132. 	 R[2][N+1]; // table for storing results (2 rows for odd- and even-length palindromes
  133.  
  134. 	 s = "@" + s + "#"; // insert 'guards' to iterate easily over s
  135.  
  136. 	 for(j = 0; j <= 1; j++)
  137. 	  {
  138. 		R[j][0] = rp = 0; i = 1;
  139.  
  140. 	    while(i <= N)
  141. 	    {
  142. 	      while(s[i - rp - 1] == s[i + j + rp]) rp++;
  143. 	      R[j][i] = rp;
  144. 	      k = 1;
  145. 	      while((R[j][i - k] != rp - k) && (k < rp))
  146. 	      {
  147. 	        R[j][i + k] = min(R[j][i - k],rp - k);
  148. 	        k++;
  149. 	      }
  150. 	      rp = max(rp - k,0);
  151. 	      i += k;
  152. 	    }
  153. 	 }
  154.  
  155. 	  s = s.substr(1,N); // remove 'guards'
  156.  
  157. 	 for(i = 1; i <= N; i++)
  158. 	 {
  159. 		for(j = 0; j <= 1; j++)
  160. 			for(rp = R[j][i]; rp > 0; rp--)
  161. 			{
  162. 				int begin = i - rp - 1;
  163. 				int end_count = 2 * rp + j;
  164. 				int end = begin + end_count - 1;
  165. 			   if (!(begin == 0  && end == N -1 ))
  166. 			   {
  167. 				   long long hsh = hash<string>{}(s.substr(begin, end_count));
  168. 				   palins[begin].push_back({end_count - 1, hsh });
  169.  
  170. 			   }
  171. 		  }
  172. 	 }
  173. }
  174.  
  175. int main()
  176. {
  177. 	string s;
  178. 	cin  >> s;
  179.  
  180. 	int start_s = clock();
  181.  
  182. 	buildSuffixArray(s, s.length());
  183. 	int n = suffixArr.size();
  184.  
  185. 	int count = 0;
  186.  
  187. 	get_palins(s);
  188.  
  189. 	// Loops through the suffix array to find all substrings
  190. 	for(int i = 0;i < n;i++)  {
  191.  
  192. 		int begin_suffix = suffixArr[i];
  193. 		int end_suffix = n - suffixArr[i];
  194.  
  195. 		for (int j = 2; j <= end_suffix; j++)
  196. 		{
  197. 			int left = begin_suffix;
  198. 			int right = begin_suffix + j - 1;
  199.  
  200. 			count += isPalin(s, left, right);
  201. 		}
  202. 	}
  203.  
  204. 	cout << count  <<  endl;
  205.  
  206. 	for (int i = 0; i < MAX+5; i++)
  207. 		palins[i].clear();
  208. 	suffixArr.clear();
  209.  
  210. 	int stop_s = clock();
  211. 	float run_time = (stop_s - start_s) / double(CLOCKS_PER_SEC);
  212. 	cout << endl << "palindromic borders  \t\tExecution time = " << run_time << " seconds" << endl;
  213.  
  214.  
  215.   return 0;
  216. }
  217.  
Success #stdin #stdout 0s 4652KB
comments (?)
stdin
copy 
ababa
stdout
copy 
5

palindromic borders  		Execution time = 0.000155 seconds
https://ideone.com/ZkiWAD
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!