Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- /*
- Suffix array implementation using bucket sorting + lcp.
- Complexity O(n log n), str[] is the target string,
- n is its length and suffix[i] contains i'th sorted suffix position.
- */
- const int MAXN = 1 << 20;
- const int MAXL = 20;
- int n, stp, mv, suffix[MAXN], tmp[MAXN];
- int sum[MAXN], cnt[MAXN], Rank[MAXL][MAXN];
- char str[MAXN];
- inline bool Equal(const int &u, const int &v){
- if(!stp) return str[u] == str[v];
- if(Rank[stp-1][u] != Rank[stp-1][v]) return false;
- int a = u + mv < n ? Rank[stp-1][u+mv] : -1;
- int b = v + mv < n ? Rank[stp-1][v+mv] : -1;
- return a == b;
- }
- void update(){
- int i, rnk;
- for(i = 0; i < n; i++) sum[i] = 0;
- for(i = rnk = 0; i < n; i++) {
- suffix[i] = tmp[i];
- if(i && !Equal(suffix[i], suffix[i-1])) {
- Rank[stp][suffix[i]] = ++rnk;
- sum[rnk+1] = sum[rnk];
- }
- else Rank[stp][suffix[i]] = rnk;
- sum[rnk+1]++;
- }
- }
- void Sort() {
- int i;
- for(i = 0; i < n; i++) cnt[i] = 0;
- memset(tmp, -1, sizeof tmp);
- for(i = 0; i < mv; i++){
- int idx = Rank[stp - 1][n - i - 1];
- int x = sum[idx];
- tmp[x + cnt[idx]] = n - i - 1;
- cnt[idx]++;
- }
- for(i = 0; i < n; i++){
- int idx = suffix[i] - mv;
- if(idx < 0)continue;
- idx = Rank[stp-1][idx];
- int x = sum[idx];
- tmp[x + cnt[idx]] = suffix[i] - mv;
- cnt[idx]++;
- }
- update();
- return;
- }
- inline bool cmp(const int &a, const int &b){
- if(str[a]!=str[b]) return str[a]<str[b];
- return false;
- }
- void SortSuffix() {
- int i;
- n =strlen(str);
- for(i = 0; i < n; i++) tmp[i] = i;
- sort(tmp, tmp + n, cmp);
- stp = 0;
- update();
- ++stp;
- for(mv = 1; mv < n; mv <<= 1) {
- Sort();
- stp++;
- }
- stp--;
- for(i = 0; i <= stp; i++) Rank[i][n] = -1;
- }
- inline int lcp(int u, int v) {
- if(u == v) return n - u;
- int ret, i;
- for(ret = 0, i = stp; i >= 0; i--) {
- if(Rank[i][u] == Rank[i][v]) {
- ret += 1<<i;
- u += 1<<i;
- v += 1<<i;
- }
- }
- return ret;
- }
- /**
- PROBLEM: Find the largest rectangular area possible
- in a given histogram where the largest rectangle
- can be made of a number of contiguous bars.
- Solution:
- For every bar X, we calculate the area with X
- as the smallest bar in the rectangle. Traverse
- all bars from left to right, maintain a stack of bars.
- Every bar is pushed to stack once. A bar is popped from stack
- when a bar of smaller height is seen. When a bar is popped,
- we calculate the area with the popped bar as smallest bar.
- Space Complexity : O(n)
- Time Complexity : O(n)
- Tested: LightOj
- **/
- #define MAX 400000
- long long st[MAX] , top;
- //given array must have zero as first element
- // n+1 element with first zero
- long long histogram(int a[], int n)
- {
- top=0;
- long long i=1, res=0;
- a[++n]=0, st[top]=0;
- while(i<=n){
- if(a[st[top]]<=a[i]) st[++top]=i++;
- else{
- long long bar = a[st[top]];
- --top;
- res = max ( res , (i-st[top]-1)*bar+bar);
- }
- }
- return res;
- }
- int a[MAXN];
- char valid[MAXN];
- int main(){
- // freopen("in.txt","r",stdin);
- cin>>n;
- cin>>str;
- cin>>valid;
- reverse(str,str+n);
- SortSuffix();
- vector < int > ans;
- long long res=0;
- for(int i=0;i<n;i++){
- if(valid[suffix[i]]=='0') {
- ans.push_back(suffix[i]);
- res = max(res,0ll+n-suffix[i]);
- }
- }
- a[0]=0;
- for(int i=1;i<ans.size();i++){
- a[i] = lcp(ans[i],ans[i-1]);
- // cout<<a[i-1];
- }
- // cout<<endl;
- // cout<<res<<endl;
- cout<<max(res,0ll+histogram(a,ans.size()))<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement