[CF873F]Forbidden Indices

2024-03-16 23:18

文章标签 forbidden indices cf873f

本文主要是介绍[CF873F]Forbidden Indices，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Forbidden Indices

题解

其实是蛮简单的一道题。

首先我们应该很容易想到后缀数组，我们可以通过LCP来求出子串的出现次数。于是，就先跑一遍后缀数组。
此时，我们就得到了相邻两个串的 $h_{i}$ ，由于后缀 $s_{i}$ 与后缀 $s_{j}$ 之间的相同前缀是等于他们之间的所有 $h$ 的最小值的，我们很容易想到滑动窗口。
我们可以通过单调栈来求出最后的答案，将它可以到达的左右边界求出来。
注意到它还有一个禁止某一位的要求，我们可以先将整个串反过来，此时答案是不会变的。条件从某一位停止就变成禁止从某一位开始了。此时将所有的被禁止的起点给删掉，再跑单调栈即可。

时间复杂度 $O\left((26+log_{n})n \right)$ 。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define MAXN 200005
typedef long long LL;
#define int LL
const LL INF=0x7f7f7f7f7f7f7f7f;
typedef pair<int,int> pii;
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while('0'>s||'9'<s){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
} 
char str[MAXN];
int n,x[MAXN],y[MAXN],c[MAXN],z[MAXN],m,sta[MAXN],stak,minn;LL ans;
int sa[MAXN],rk[MAXN],hei[MAXN],ban[MAXN],L[MAXN],R[MAXN],hh[MAXN],cur;
void getSa(){for(int i=1;i<=n;i++)c[x[i]=str[i]-'a'+1]++;for(int i=2;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>0;i--)sa[c[x[i]]--]=i;//for(int i=1;i<=n;i++)printf("%d ",sa[i]);puts("");for(int k=1;k<=n;k<<=1){int num=0;for(int i=n-k+1;i<=n;i++)y[++num]=i;for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;for(int i=1;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[z[i]=x[i]]++;for(int i=2;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>0;i--)sa[c[x[y[i]]]--]=y[i];for(int i=1;i<=n;i++)x[i]=y[i]=0;x[sa[1]]=num=1;for(int i=2;i<=n;i++)x[sa[i]]=(z[sa[i]]==z[sa[i-1]]&&z[sa[i]+k]==z[sa[i-1]+k])?num:++num;//for(int i=1;i<=n;i++)printf("%d ",sa[i]);puts("");m=num;if(num==n)break;}
}
void getHi(){int k=0;for(int i=1;i<=n;i++)rk[sa[i]]=i;for(int i=1;i<=n;i++){if(k)k--;int j=sa[rk[i]-1];while(i+k<=n&&j+k<=n&&str[i+k]==str[j+k])k++;hei[rk[i]]=k;}//for(int i=1;i<=n;i++)printf("%d\n",hei[i]);
} 
signed main(){read(n);scanf("\n%s",str+1);m=26;getSa();getHi();for(int i=n;i>0;i--)scanf("%1lld",&ban[i]);ban[0]=1;for(int i=1;i<=n;i++){if(!ban[sa[i]])ans=max(ans,1ll*(n-sa[i]+1));if(ban[sa[i]])minn=min(minn,hei[i]);else if(!ban[sa[i]]&&ban[sa[i-1]])hh[++cur]=min(minn,hei[i]),minn=INF;else hh[++cur]=hei[i];}for(int i=1;i<=cur;i++){while(stak&&hh[sta[stak]]>=hh[i])R[sta[stak--]]=i;L[i]=stak?sta[stak]:1;sta[++stak]=i;}while(stak)R[sta[stak--]]=cur+1;for(int i=1;i<=cur;i++)ans=max(ans,1ll*hh[i]*(R[i]-L[i]));printf("%lld\n",ans);return 0;
}