fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <stdio.h>
  4. #include <algorithm>
  5. #include <string.h>
  6.  
  7. using namespace std;
  8.  
  9. #define FOR(i,a,b) for(int i=a;i<b;i++)
  10. #define REP(i,b) FOR(i,0,b)
  11.  
  12. const int Nmax = 1000001;
  13. int bucket[Nmax];
  14.  
  15. template <class T>
  16. void CreateBeginBucket(T* data, int size, int maxVal){
  17. 	REP(i, maxVal + 1) bucket[i] = 0;
  18. 	REP(i, size) bucket[data[i]]++;
  19. 	int sum = 0;
  20. 	REP(i, maxVal + 1){ bucket[i] += sum; swap(bucket[i], sum); }
  21. }
  22.  
  23. template <class T>
  24. void CreateEndBucket(T* data, int size, int maxVal){
  25. 	REP(i, maxVal + 1) bucket[i] = 0;
  26. 	REP(i, size) bucket[data[i]]++;
  27. 	int sum = 0;
  28. 	REP(i, maxVal + 1){ sum += bucket[i]; bucket[i] = sum; }
  29. }
  30.  
  31. template<class T>
  32. void InducedSort(T* data, int size, int* SA, int maxVal, bool* isL){
  33. 	CreateBeginBucket(data, size, maxVal);
  34. 	REP(i, size) if (SA[i] > 0 && isL[SA[i] - 1]) SA[bucket[data[SA[i] - 1]]++] = SA[i] - 1;
  35. }
  36.  
  37. template<class T>
  38. void InvertInducedSort(T* data, int size, int* SA, int maxVal, bool* isL){
  39. 	CreateEndBucket(data, size, maxVal);
  40. 	for (int i = size - 1; i >= 0; --i) if (SA[i] > 0 && !isL[SA[i] - 1]) SA[--bucket[data[SA[i] - 1]]] = SA[i] - 1;
  41. }
  42.  
  43. template <class T>
  44. void DBGOUT(T* sa, int size){
  45. 	REP(i, size) printf("%d ", int(sa[i]));
  46. 	printf("\n");
  47. }
  48.  
  49. template<class T>
  50. void SA_IS(T* data, int size, int* SA, int maxVal, bool* isL){
  51. 	REP(i, size) SA[i] = -1;
  52. #define isLMS(x) (x>0 && isL[x-1] && !isL[x])
  53. 	isL[size - 1] = false;
  54. 	for (int i = size - 2; i >= 0; i--) isL[i] = data[i] > data[i + 1] || (data[i] == data[i + 1] && isL[i + 1]);
  55. 	CreateEndBucket(data, size, maxVal);
  56. 	FOR(i, 1, size) if (isLMS(i)) SA[--bucket[data[i]]] = i;
  57. 	InducedSort(data, size, SA, maxVal, isL);
  58. 	InvertInducedSort(data, size, SA, maxVal, isL);
  59.  
  60. 	int c = 0;
  61. 	REP(i, size) if (isLMS(SA[i])) SA[c++] = SA[i];
  62. 	FOR(i, c, size) SA[i] = -1;
  63.  
  64. 	int idx = -1;
  65. 	int prev = -1;
  66. 	REP(i, c){
  67. 		bool diff = false;
  68. 		REP(d, size){
  69. 			if (prev == -1 || data[SA[i] + d] != data[prev + d] || isL[SA[i] + d] != isL[prev + d]){
  70. 				diff = true;
  71. 				break;
  72. 			}
  73. 			else if (d > 0 && isLMS(SA[i] + d)) break;
  74. 		}
  75. 		if (diff){ idx++; prev = SA[i]; }
  76. 		SA[c + SA[i] / 2] = idx;
  77. 	}
  78. 	int j = size;
  79. 	for (int i = size - 1; i >= c; i--) if (SA[i] >= 0) SA[--j] = SA[i];
  80.  
  81. 	int* nxdata = SA + size - c;
  82. 	int* nxsa = SA;
  83. 	if (c == idx + 1) REP(i, c) nxsa[nxdata[i]] = i;
  84. 	else SA_IS(nxdata, c, nxsa, idx, isL + size);
  85.  
  86. 	j = c;
  87. 	for (int i = size - 1; i >= 1; i--) if (isLMS(i)) nxdata[--j] = i;
  88. 	REP(i, c) nxsa[i] = nxdata[nxsa[i]];
  89. 	FOR(i, c, size) SA[i] = -1;
  90. 	CreateEndBucket(data, size, maxVal);
  91. 	for (int i = c - 1; i >= 0; i--) swap(nxsa[i], SA[--bucket[data[nxsa[i]]]]);
  92. 	InducedSort(data, size, SA, maxVal, isL);
  93. 	InvertInducedSort(data, size, SA, maxVal, isL);
  94. }
  95.  
  96. bool isLPool[Nmax * 2];
  97. void SA_IS(unsigned char* input, int size, int* SA){
  98. 	int mv = 0;
  99. 	REP(i, size) if (mv < input[i]) mv = input[i];
  100. 	SA_IS(input, size, SA, mv, isLPool);
  101. }
  102.  
  103. int lcp[Nmax];
  104. int invertSA[Nmax];
  105. void CreateLCP(unsigned char* data, int size, int* SA){
  106. 	lcp[0] = -1;
  107. 	REP(i, size) invertSA[SA[i]] = i;
  108. 	int prev = 0;
  109. 	REP(i, size){
  110. 		if (invertSA[i] > 0){
  111. 			while (data[i + prev] == data[SA[invertSA[i] - 1] + prev]){
  112. 				++prev;
  113. 				if (i + prev >= size || SA[invertSA[i] - 1] + prev >= size)
  114. 					break;
  115. 			}
  116. 			lcp[invertSA[i]] = prev;
  117. 		}
  118. 		prev = max(prev - 1, 0);
  119. 	}
  120. }
  121.  
  122. int st[21][Nmax];
  123. void InitSparseTable(int n){
  124. 	int h = 1;
  125. 	while ((1 << h) < n) h++;
  126. 	REP(i, n) st[0][i] = lcp[i];
  127. 	FOR(j, 1, h + 1){
  128. 		REP(i, n - (1<<j) + 1){
  129. 			st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
  130. 		}
  131. 	}
  132. }
  133.  
  134. inline int TopBit(int t){
  135. 	for (int i = 20; i >= 0; i--){
  136. 		if ((1 << i)&t) return i;
  137. 	}
  138. 	return -1;
  139. }
  140.  
  141. int GetLCP(int f, int s){
  142. 	if (f > s) swap(f, s);
  143. 	int diff = TopBit(s-f);
  144. 	return min(st[diff][f], st[diff][s - (1 << diff)]);
  145. }
  146.  
  147. unsigned char str[Nmax];
  148. int indices[Nmax];
  149.  
  150. int compare(int f, int s, int l){
  151. 	int fi = invertSA[f];
  152. 	int si = invertSA[s];
  153. 	if (GetLCP(fi + 1, si + 1) >= l)
  154. 		return 0;
  155. 	else
  156. 		return 2 * (fi > si) - 1;
  157. }
  158.  
  159. int dpd[Nmax];
  160. int main(){
  161. 	int n;
  162. 	scanf("%d", &n);
  163. 	scanf("%s", str);
  164. 	SA_IS(str, n + 1, indices);
  165. 	CreateLCP(str, n + 1, indices);
  166. 	InitSparseTable(n + 1);
  167. 	fill(dpd, dpd + n + 1, 1000000000);
  168. 	int* dp = dpd + 1;
  169. 	dp[n - 2] = 1;
  170. 	int ans = 1000000000;
  171. 	for (int i = n - 2; i >= 0; i--){
  172. 		if (str[i + 1] != '0'){
  173. 			int nx = i - dp[i];
  174. 			if (nx >= -1){
  175. 				if (compare(nx + 1, i + 1, dp[i]) <= 0){
  176. 					nx--;
  177. 				}
  178. 				if (nx >= -1){
  179. 					dp[nx] = min(dp[nx], i - nx);
  180. 				}
  181. 			}
  182. 		}
  183. 		dp[i - 1] = min(dp[i - 1], dp[i] + 1);
  184. 	}
  185. 	printf("%d\n", dp[-1]);
  186. }
  187.  
Success #stdin #stdout 0s 107968KB
comments (?)
stdin
copy 
20
49260520598009034978
stdout
copy 
8
https://ideone.com/VnBQd8
language:
C++ (gcc 8.3)
created:
8 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!