fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 100000
  4. #define LL long long 
  5. int Rank[20][MAX];
  6. int arr[100000],cum[100000],lcp[100000];
  7. struct Tuple
  8. {
  9. 	int left,right,pos;
  10. };
  11. bool compare(const Tuple &a, const Tuple &b)
  12. {
  13. 	return a.left == b.left ? a.right < b.right : a.left < b.left;
  14. }
  15. void counting_sort(Tuple t[] , int n)
  16. {
  17. 	int count[MAX+9];
  18. 	Tuple temp[n + 9];
  19. 	memset(count , 0 , sizeof count);
  20.  
  21. 	for(int i = 0 ;i < n ; i++)
  22. 		count[t[i].right + 1]++;
  23.  
  24. 	for(int i = 1 ; i  < MAX ; i++)
  25. 		count[i] += count[i-1];
  26.  
  27. 	for(int i = 0 ; i<n ; i++)
  28. 	{
  29. 		temp[count[t[i].right +1] - 1] = t[i];
  30. 		count[t[i].right + 1]--;
  31. 	}	
  32.  
  33. 	memset(count , 0 , sizeof count);
  34.  
  35. 	for(int i = 0 ; i < n ; i ++)
  36. 		count[t[i].left + 1] ++;
  37.  
  38. 	for(int i = 1 ; i<MAX ; i++)
  39. 		count[i] += count[i-1];
  40.  
  41. 	for(int i = n- 1; i>=0 ; i--)
  42. 	{
  43. 		t[count[temp[i].left + 1] - 1] = temp[i];
  44. 		count[temp[i].left + 1]--;
  45. 	}
  46. }
  47. void suffix_array(char s[],int n)
  48. {
  49.  
  50. 	for(int i=0;i<n;i++)
  51. 		Rank[0][i] = s[i] - 97;
  52.  
  53. 	Tuple t[n+9];
  54.  
  55.  
  56. 	for(int stp = 1 , cnt = 1 ; (cnt>>1) < n ; cnt<<=1 , stp++)
  57. 	{
  58. 		for(int i=0;i<n;i++)
  59. 		{
  60. 			t[i].left = Rank[stp-1][i];
  61. 			t[i].right = i+cnt < n ? Rank[stp-1][i + cnt] : -1;
  62. 			t[i].pos = i;
  63. 		}
  64. 		//sort(t,t+n,compare);
  65. 		counting_sort(t , n);
  66. 		for(int i=0;i<n;i++)
  67. 			Rank[stp][t[i].pos] = i > 0 && t[i-1].left == t[i].left && t[i-1].right == t[i].right ? Rank[stp][t[i-1].pos] : i;
  68. 	}
  69. 	int pos = ceil(log(n)/log(2));
  70. 	for(int i = 0;i<n;i++)
  71. 		arr[Rank[pos][i]] = i;
  72. }
  73. int LCP(int i,int j,int n)
  74. {
  75. 	int count = 0;
  76. 	if(i == j)
  77. 		return n - i;
  78. 	for(int stp = ceil(log(n)/log(2)) ; stp >= 0 && i < n && j < n ; stp --)
  79. 		if(Rank[stp][i] == Rank[stp][j])
  80. 		{
  81. 			count += 1<<stp;
  82. 			i += 1<<stp;
  83. 			j += 1<<stp;
  84. 		}
  85. 	return count;
  86. }
  87. void lcpArray(int sa[],int n)
  88. {
  89. 	lcp[0] = 0;
  90. 	for(int i = 1;i<n;i++)
  91. 		lcp[i] = LCP(sa[i - 1] , sa[i],n);
  92.  
  93. }
  94. int main()
  95. {
  96. 	char s[100000];
  97. 	scanf("%s",s);
  98. 	int  n = strlen(s);
  99. 	suffix_array(s,n);
  100. 	lcpArray(arr , n);
  101. 	cum[0] = n - arr[0];
  102. 	for(int i = 1;i < n;i++){
  103. 		cum[i] = cum[i-1] + (n - arr[i] - lcp[i]);
  104. 	}
  105. 	int q;
  106. 	scanf("%d",&q);
  107. 	while(q--)
  108. 	{
  109. 		int a ;
  110. 		scanf("%d",&a);
  111. 		int pos ;
  112. 		pos = lower_bound(cum , cum + n , a) - cum;
  113. 		int i , j;
  114. 		for(int j = 0 , i = arr[pos] ; j< a - cum[pos-1] + lcp[pos] ; j++,i++)
  115. 			printf("%c",s[i]);
  116. 		printf("\n");
  117. 	}
  118. 	return 0;
  119. }
Runtime error #stdin #stdout 0.03s 11696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/8dy7Yq
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!