Advertisement
Guest User

Untitled

a guest
Oct 24th, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.84 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. /*
  4. Suffix array implementation using bucket sorting + lcp.
  5. Complexity O(n log n), str[] is the target string,
  6. n is its length and suffix[i] contains i'th sorted suffix position.
  7. */
  8.  
  9. const int MAXN = 1 << 20;
  10. const int MAXL = 20;
  11.  
  12. int n, stp, mv, suffix[MAXN], tmp[MAXN];
  13. int sum[MAXN], cnt[MAXN], Rank[MAXL][MAXN];
  14. char str[MAXN];
  15.  
  16. inline bool Equal(const int &u, const int &v){
  17. if(!stp) return str[u] == str[v];
  18. if(Rank[stp-1][u] != Rank[stp-1][v]) return false;
  19. int a = u + mv < n ? Rank[stp-1][u+mv] : -1;
  20. int b = v + mv < n ? Rank[stp-1][v+mv] : -1;
  21. return a == b;
  22. }
  23.  
  24. void update(){
  25. int i, rnk;
  26. for(i = 0; i < n; i++) sum[i] = 0;
  27. for(i = rnk = 0; i < n; i++) {
  28. suffix[i] = tmp[i];
  29. if(i && !Equal(suffix[i], suffix[i-1])) {
  30. Rank[stp][suffix[i]] = ++rnk;
  31. sum[rnk+1] = sum[rnk];
  32. }
  33. else Rank[stp][suffix[i]] = rnk;
  34. sum[rnk+1]++;
  35. }
  36. }
  37.  
  38. void Sort() {
  39. int i;
  40. for(i = 0; i < n; i++) cnt[i] = 0;
  41. memset(tmp, -1, sizeof tmp);
  42. for(i = 0; i < mv; i++){
  43. int idx = Rank[stp - 1][n - i - 1];
  44. int x = sum[idx];
  45. tmp[x + cnt[idx]] = n - i - 1;
  46. cnt[idx]++;
  47. }
  48. for(i = 0; i < n; i++){
  49. int idx = suffix[i] - mv;
  50. if(idx < 0)continue;
  51. idx = Rank[stp-1][idx];
  52. int x = sum[idx];
  53. tmp[x + cnt[idx]] = suffix[i] - mv;
  54. cnt[idx]++;
  55. }
  56. update();
  57. return;
  58. }
  59.  
  60. inline bool cmp(const int &a, const int &b){
  61. if(str[a]!=str[b]) return str[a]<str[b];
  62. return false;
  63. }
  64.  
  65. void SortSuffix() {
  66. int i;
  67. n =strlen(str);
  68. for(i = 0; i < n; i++) tmp[i] = i;
  69. sort(tmp, tmp + n, cmp);
  70. stp = 0;
  71. update();
  72. ++stp;
  73. for(mv = 1; mv < n; mv <<= 1) {
  74. Sort();
  75. stp++;
  76. }
  77. stp--;
  78. for(i = 0; i <= stp; i++) Rank[i][n] = -1;
  79. }
  80.  
  81. inline int lcp(int u, int v) {
  82. if(u == v) return n - u;
  83. int ret, i;
  84. for(ret = 0, i = stp; i >= 0; i--) {
  85. if(Rank[i][u] == Rank[i][v]) {
  86. ret += 1<<i;
  87. u += 1<<i;
  88. v += 1<<i;
  89. }
  90. }
  91. return ret;
  92. }
  93.  
  94.  
  95.  
  96.  
  97. /**
  98. PROBLEM: Find the largest rectangular area possible
  99. in a given histogram where the largest rectangle
  100. can be made of a number of contiguous bars.
  101.  
  102. Solution:
  103. For every bar X, we calculate the area with X
  104. as the smallest bar in the rectangle. Traverse
  105. all bars from left to right, maintain a stack of bars.
  106. Every bar is pushed to stack once. A bar is popped from stack
  107. when a bar of smaller height is seen. When a bar is popped,
  108. we calculate the area with the popped bar as smallest bar.
  109.  
  110.  
  111. Space Complexity : O(n)
  112. Time Complexity : O(n)
  113. Tested: LightOj
  114. **/
  115. #define MAX 400000
  116.  
  117.  
  118. long long st[MAX] , top;
  119. //given array must have zero as first element
  120. // n+1 element with first zero
  121. long long histogram(int a[], int n)
  122. {
  123. top=0;
  124. long long i=1, res=0;
  125. a[++n]=0, st[top]=0;
  126. while(i<=n){
  127. if(a[st[top]]<=a[i]) st[++top]=i++;
  128. else{
  129. long long bar = a[st[top]];
  130. --top;
  131. res = max ( res , (i-st[top]-1)*bar+bar);
  132. }
  133. }
  134. return res;
  135. }
  136. int a[MAXN];
  137. char valid[MAXN];
  138. int main(){
  139. // freopen("in.txt","r",stdin);
  140. cin>>n;
  141. cin>>str;
  142. cin>>valid;
  143. reverse(str,str+n);
  144. SortSuffix();
  145. vector < int > ans;
  146. long long res=0;
  147. for(int i=0;i<n;i++){
  148. if(valid[suffix[i]]=='0') {
  149. ans.push_back(suffix[i]);
  150. res = max(res,0ll+n-suffix[i]);
  151. }
  152. }
  153. a[0]=0;
  154. for(int i=1;i<ans.size();i++){
  155. a[i] = lcp(ans[i],ans[i-1]);
  156. // cout<<a[i-1];
  157.  
  158. }
  159. // cout<<endl;
  160. // cout<<res<<endl;
  161.  
  162.  
  163. cout<<max(res,0ll+histogram(a,ans.size()))<<endl;
  164.  
  165. return 0;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement