fork(9) download
copy 
  1. /*tested:
  2.     author:Ritesh K Gupta 
  3.     http://w...content-available-to-author-only...j.pl/problems/LPS/
  4.  
  5. */
  6. #include <stdio.h>
  7. #include <algorithm>
  8. #include <iostream>
  9. #include <string>
  10. #include <cstring>
  11. #include <cmath>
  12. #define MAX 1000000
  13. using namespace std;
  14. char str[MAX]; //input
  15. int Rank[MAX], suffixArray[MAX]; //output
  16. int cnt[MAX], Next[MAX]; //internal
  17. char original[MAX];
  18. bool bh[MAX], b2h[MAX];
  19. int Height[MAX];
  20. int Length_of_str;
  21. /*The format for M table where preprocessing value are stored is
  22. M[MAX_STRING_SIZE][logbase2(MAX_STRING_SIZE)].
  23. Also it it observed that Value of logbase2(10^7)= 23.253496664.
  24. Thus always fix logbase2 value to 25.
  25. */
  26.  
  27. int M[MAX][25];
  28.  
  29. bool smaller_first_char(int a, int b)
  30. {
  31. 	return str[a] < str[b];
  32. }
  33. void print(int index)
  34. {
  35. 	for(int i=index;i<strlen(str);++i)
  36. 	{
  37. 		cout<<str[i];
  38. 	}
  39. 	cout<<endl;
  40. }
  41.  
  42. void suffixSort(int n)
  43. {
  44. 	//sort suffixes according to their first characters
  45. 	for (int i=0; i<n; ++i)
  46. 	{
  47. 		suffixArray[i] = i;
  48. 	}
  49. 	sort(suffixArray, suffixArray + n, smaller_first_char);
  50. 	//{suffixArray contains the list of suffixes sorted by their first character}
  51.  
  52. 	for (int i=0; i<n; ++i)
  53. 	{
  54. 		bh[i] = i == 0 || str[suffixArray[i]] != str[suffixArray[i-1]];
  55. 		b2h[i] = false;
  56. 	}
  57.  
  58. 	for (int h = 1; h < n; h <<= 1)
  59. 	{
  60. 		//{bh[i] == false if the first h characters of suffixArray[i-1] == the first h characters of suffixArray[i]}
  61. 		int buckets = 0;
  62. 		for (int i=0, j; i < n; i = j)
  63. 		{
  64. 			j = i + 1;
  65. 			while (j < n && !bh[j]) j++;
  66. 			Next[i] = j;
  67. 			buckets++;
  68. 		}
  69. 		if (buckets == n) break; // We are done! Lucky bastards!
  70. 		//{suffixes are separted in buckets containing strings starting with the same h characters}
  71.  
  72. 		for (int i = 0; i < n; i = Next[i])
  73. 		{
  74. 			cnt[i] = 0;
  75. 			for (int j = i; j < Next[i]; ++j)
  76. 			{
  77. 				Rank[suffixArray[j]] = i;
  78. 			}
  79. 		}
  80.  
  81. 		cnt[Rank[n - h]]++;
  82. 		b2h[Rank[n - h]] = true;
  83. 		for (int i = 0; i < n; i = Next[i])
  84. 		{
  85. 			for (int j = i; j < Next[i]; ++j)
  86. 			{
  87. 				int s = suffixArray[j] - h;
  88. 				if (s >= 0){
  89. 					int head = Rank[s];
  90. 					Rank[s] = head + cnt[head]++;
  91. 					b2h[Rank[s]] = true;
  92. 				}
  93. 			}
  94. 			for (int j = i; j < Next[i]; ++j)
  95. 			{
  96. 				int s = suffixArray[j] - h;
  97. 				if (s >= 0 && b2h[Rank[s]]){
  98. 					for (int k = Rank[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = false;
  99. 				}
  100. 			}
  101. 		}
  102. 		for (int i=0; i<n; ++i)
  103. 		{
  104. 			suffixArray[Rank[i]] = i;
  105. 			bh[i] |= b2h[i];
  106. 		}
  107. 	}
  108. 	for (int i=0; i<n; ++i)
  109. 	{
  110. 		Rank[suffixArray[i]] = i;
  111. 	}
  112. }
  113. // End of suffix array algorithm
  114.  
  115. /*
  116. Begin of the O(n) longest common prefix algorithm
  117. Refer to "Linear-Time Longest-Common-Prefix Computation in Suffix
  118. Arrays and Its Applications" by Toru Kasai, Gunho Lee, Hiroki
  119. Arimura, Setsuo Arikawa, and Kunsoo Park.
  120. */
  121.  
  122. /*
  123. Note to say Suffix [i] always means the Ith suffix in LEXOGRAPHICALLY SORTED ORDER
  124. ie Height[i]=LCPs of (Suffix   i-1 ,suffix  i)
  125. */
  126.  
  127. void getHeight(int n)
  128. {
  129. 	for (int i=0; i<n; ++i) Rank[suffixArray[i]] = i;
  130. 	Height[0] = 0;
  131. 	for (int i=0, h=0; i<n; ++i)
  132. 	{
  133. 		if (Rank[i] > 0)
  134. 		{
  135. 			int j = suffixArray[Rank[i]-1];
  136. 			while (i + h < n && j + h < n && str[i+h] == str[j+h])
  137. 			{
  138. 				h++;
  139. 			}
  140. 			Height[Rank[i]] = h;
  141. 			if (h > 0) h--;
  142. 		}
  143. 	}
  144. }
  145. // End of longest common prefixes algorithm
  146.  
  147. /*When the LCP of consecutive pair of Suffixes is Knows 
  148.  
  149. THEN:
  150. We can calculate the LCPs of any suffixes (i,j)
  151. with the Help of Following Formula
  152.  
  153. ************************************************
  154. *  LCP(suffix i,suffix j)=LCP[RMQ(i + 1; j)]   * 
  155. *                                              *
  156. *  Also Note (i<j) As LCP (suff i,suff j) may  *
  157. *  not necessarly equal LCP (Suff j,suff i).   *
  158. ************************************************
  159. */
  160.  
  161. void preprocesses(int N)
  162. {
  163. 	int i, j;
  164.  
  165. 	//initialize M for the intervals with length 1
  166. 	for (i = 0; i < N; i++)
  167. 		M[i][0] = i;
  168.  
  169. 	//compute values from smaller to bigger intervals
  170. 	for (j = 1; 1 << j <= N; j++)
  171. 	{
  172. 		for (i = 0; i + (1 << j) - 1 < N; i++)
  173. 		{
  174. 			if (Height[M[i][j - 1]] < Height[M[i + (1 << (j - 1))][j - 1]])
  175. 			{
  176. 				M[i][j] = M[i][j - 1];
  177. 			}
  178. 			else
  179. 			{
  180. 				M[i][j] = M[i + (1 << (j - 1))][j - 1];
  181. 			}
  182. 		}
  183. 	}
  184. }  
  185. int RMQ(int i,int j)
  186. {
  187. 	int k=log((double)(j-i+1))/log((double)2);
  188. 	int vv= j-(1<<k)+1 ;
  189. 	if(Height[M[i][k]]<=Height[ M[vv][ k] ])
  190. 		return M[i][k];
  191. 	else
  192. 		return M[ vv ][ k];
  193. }
  194. int LCP(int i,int j)
  195. {
  196. 	/*Make sure we send i<j always */
  197. 	/* By doing this ,it resolve following
  198. 	suppose ,we send LCP(5,4) then it converts it to LCP(4,5)
  199. 	*/
  200. 	if(i>j)
  201. 		swap(i,j);
  202.  
  203. 	/*conformation over*/
  204.  
  205. 	if(i==j)
  206. 	{
  207. 		return (abs(Length_of_str-suffixArray[i]));
  208. 	}
  209. 	else
  210. 	{
  211. 		return Height[RMQ(i+1,j)];
  212. 		//LCP(suffix i,suffix j)=LCPadj[RMQ(i + 1; j)] 
  213. 		//LCPadj=LCP of adjacent suffix =Height.
  214. 	}
  215. }
  216. int main()
  217. {
  218.  
  219. 	int Len,actuallen;
  220. 	char tc[10],Lenbuffer[10];
  221.  
  222. 	scanf("%d",&Len);
  223. 	scanf("%s",str);
  224.  
  225. 	Len=strlen(str);
  226. 	actuallen=Len;
  227.  
  228. 	strcpy(original,str);
  229. 	str[Len]='#';			//Put Marker
  230. 	str[Len+1]=0;
  231.  
  232. 	reverse(original,original+Len);
  233.  
  234. 	//Concatenate to form "string#gnirts"
  235. 	strcat(str,original);
  236.  
  237. 	//Update the Length of new string . Updated Length=Len(original)+Len(Reverse)+LenMarher (Marker '#' Len=1)
  238. 	Len=(actuallen*2)+1;
  239.  
  240. 	suffixSort(Len);
  241.  
  242. 	/*Calculate LCP of Adjacents /consecutive Suffix Pairs */
  243. 	getHeight(Len);
  244.  
  245. 	/*Calculate LCP of Any two suffixes i,j using RMQ concept */
  246. 	//preprocesses(Len);
  247.  
  248. 	/* In general we find the character just after our current position
  249. 	in the original string, and the character just before it in the reversed string, 
  250. 	and find the longest common prefix using the lcp array and RMQ
  251. 	*/
  252. 	int res=0;
  253. 	int startptr=0;
  254. 	for(int i=1;i<Len;++i)
  255. 	{
  256. 		if((Height[i]>res))
  257. 		{
  258. 			if((suffixArray[i-1]<actuallen && suffixArray[i]>actuallen)||(suffixArray[i]<actuallen && suffixArray[i-1]>actuallen))
  259. 			{
  260. 				res=Height[i];
  261. 				startptr=suffixArray[i];
  262. 			}
  263. 		}
  264. 	}
  265. 	printf("%d\n",res);
  266. 	return 0;
  267. }
  268.  
  269.  
Success #stdin #stdout 0s 123968KB
comments (?)
stdin
copy 
5
ababa
stdout
copy 
5
https://ideone.com/qryhgR
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

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!