题面
BZOJ
题解
注意看题:
要求的是 \([a,b]\)的子串和 [c,d] 的 \(lcp\)的最大值
先来一下暴力吧
求出 \(SA\)之后
暴力枚举 \([A,B]\)之间的后缀
求一个 \(lcp\)
复杂度 \(O(nm)\)
\(40\)分到手
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #include<set>
- #include<map>
- #include<vector>
- #include<queue>
- using namespace std;
- #define ll long long
- #define RG register
- #define MAX 222222
- inline int read()
- {
- RG int x=0,t=1;RG char ch=getchar();
- while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
- if(ch=='-')t=-1,ch=getchar();
- while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
- return x*t;
- }
- int lg[MAX],a[MAX];
- char s[MAX];
- int n,m;
- struct SA
- {
- int x[MAX],y[MAX],SA[MAX],t[MAX];
- int ht[MAX],rk[MAX],p[20][MAX];
- bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}
- void GetSA()
- {
- int m=50;
- for(int i=1;i<=n;++i)t[x[i]=a[i]]++;
- for(int i=1;i<=m;++i)t[i]+=t[i-1];
- for(int i=n;i;--i)SA[t[x[i]]--]=i;
- for(int k=1;k<=n;k<<=1)
- {
- int p=0;
- for(int i=n-k+1;i<=n;++i)y[++p]=i;
- for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;
- for(int i=0;i<=m;++i)t[i]=0;
- for(int i=1;i<=n;++i)t[x[y[i]]]++;
- for(int i=1;i<=m;++i)t[i]+=t[i-1];
- for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];
- swap(x,y);
- x[SA[1]]=p=1;
- for(int i=2;i<=n;++i)x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;
- if(p>=n)break;
- m=p;
- }
- for(int i=1;i<=n;++i)rk[SA[i]]=i;
- for(int i=1,j=0;i<=n;++i)
- {
- if(j)--j;
- while(a[i+j]==a[SA[rk[i]-1]+j])++j;
- ht[rk[i]]=j;
- }
- }
- void prepare()
- {
- for(int i=1;i<=n;++i)p[0][i]=ht[i];
- for(int j=1;j<17;++j)
- for(int i=1;i<=n;++i)
- p[j][i]=min(p[j-1][i],p[j-1][i+(1<<(j-1))]);
- }
- int rmq(int l,int r){return min(p[lg[r-l+1]][l],p[lg[r-l+1]][r-(1<<lg[r-l+1])+1]);}
- int lcp(int l,int r)
- {
- if(l==r)return n-l+1;
- if(rk[l]>rk[r])swap(l,r);
- return rmq(rk[l]+1,rk[r]);
- }
- }SA;
- int main()
- {
- n=read();m=read();
- scanf("%s",s+1);
- for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
- for(int i=1;i<=n;++i)a[i]=s[i]-96;
- SA.GetSA();
- SA.prepare();
- while(m--)
- {
- int A=read(),B=read(),C=read(),D=read();
- int ans=0;
- for(int i=A;i<=B;++i)ans=max(ans,min(min(D-C+1,B-i+1),SA.lcp(i,C)));
- printf("%d\n",ans);
- }
- return 0;
- }
我是真的垃圾
不会做
确定了 \(C\)之后
二分一个答案 \(mid\)
那么, 可以确定必须要在一个区间内存在 \([A,B]\)中某个位置的 \(rank\)
那么, 二分出满足 \(lcp\)大于 \(mid\)的区间
然后查询是否满足条件即可
查询使用主席树来做
- #include < iostream > #include < cstdio > #include < cstdlib > #include < cstring > #include < cmath > #include < algorithm > #include < set > #include < map > #include < vector > #include < queue > using namespace std;#define ll long long#define RG register#define MAX 222222 inline int read() {
- RG int x = 0,
- t = 1;
- RG char ch = getchar();
- while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
- if (ch == '-') t = -1,
- ch = getchar();
- while (ch <= '9' && ch >= '0') x = x * 10 + ch - 48,
- ch = getchar();
- return x * t;
- }
- int lg[MAX],
- a[MAX];
- char s[MAX];
- int n,
- m;
- struct President_SegMent_Tree {
- struct Node {
- int ls,
- rs;
- int v;
- }
- t[MAX << 5];
- int tot,
- rt[MAX];
- void Modify(int & now, int ff, int l, int r, int p, int w) {
- now = ++tot;
- t[now] = t[ff];
- t[now].v += w;
- if (l == r) return;
- int mid = (l + r) >> 1;
- if (p <= mid) Modify(t[now].ls, t[ff].ls, l, mid, p, w);
- else Modify(t[now].rs, t[ff].rs, mid + 1, r, p, w);
- }
- int Query(int r1, int r2, int l, int r, int L, int R) {
- if (L <= l && r <= R) {
- return t[r2].v - t[r1].v;
- }
- int mid = (l + r) >> 1,
- ret = 0;
- if (L <= mid) ret += Query(t[r1].ls, t[r2].ls, l, mid, L, R);
- if (R > mid) ret += Query(t[r1].rs, t[r2].rs, mid + 1, r, L, R);
- return ret;
- }
- }
- seg;
- struct SA {
- int x[MAX],
- y[MAX],
- SA[MAX],
- t[MAX];
- int ht[MAX],
- rk[MAX],
- p[20][MAX];
- bool cmp(int i, int j, int k) {
- return y[i] == y[j] && y[i + k] == y[j + k];
- }
- void GetSA() {
- int m = 50;
- for (int i = 1; i <= n; ++i) t[x[i] = a[i]]++;
- for (int i = 1; i <= m; ++i) t[i] += t[i - 1];
- for (int i = n; i; --i) SA[t[x[i]]--] = i;
- for (int k = 1; k <= n; k <<= 1) {
- int p = 0;
- for (int i = n - k + 1; i <= n; ++i) y[++p] = i;
- for (int i = 1; i <= n; ++i) if (SA[i] > k) y[++p] = SA[i] - k;
- for (int i = 0; i <= m; ++i) t[i] = 0;
- for (int i = 1; i <= n; ++i) t[x[y[i]]]++;
- for (int i = 1; i <= m; ++i) t[i] += t[i - 1];
- for (int i = n; i >= 1; --i) SA[t[x[y[i]]]--] = y[i];
- swap(x, y);
- x[SA[1]] = p = 1;
- for (int i = 2; i <= n; ++i) x[SA[i]] = cmp(SA[i], SA[i - 1], k) ? p: ++p;
- if (p >= n) break;
- m = p;
- }
- for (int i = 1; i <= n; ++i) rk[SA[i]] = i;
- for (int i = 1, j = 0; i <= n; ++i) {
- if (j)--j;
- while (a[i + j] == a[SA[rk[i] - 1] + j])++j;
- ht[rk[i]] = j;
- }
- }
- void prepare() {
- for (int i = 1; i <= n; ++i) p[0][i] = ht[i];
- for (int j = 1; j < 19; ++j) for (int i = 1; i <= n; ++i) p[j][i] = min(p[j - 1][i], p[j - 1][i + (1 << (j - 1))]);
- }
- int rmq(int l, int r) {
- if (l == r) return 1e9; ++l;
- return min(p[lg[r - l + 1]][l], p[lg[r - l + 1]][r - (1 << lg[r - l + 1]) + 1]);
- }
- bool check(int len, int A, int B, int C, int D) {
- int l,
- r,
- L = rk[C],
- R = rk[C];
- l = 1,
- r = rk[C];
- while (l < r) {
- int mid = (l + r) >> 1;
- if (rmq(mid, rk[C]) >= len) r = mid;
- else l = mid + 1;
- }
- L = l;
- l = rk[C],
- r = n;
- while (l < r) {
- int mid = (l + r + 1) >> 1;
- if (rmq(rk[C], mid) >= len) l = mid;
- else r = mid - 1;
- }
- R = l;
- return seg.Query(seg.rt[L - 1], seg.rt[R], 1, n, A, B - len + 1);
- }
- }
- SA;
- int main() {
- n = read();
- m = read();
- scanf("%s", s + 1);
- for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
- for (int i = 1; i <= n; ++i) a[i] = s[i] - 96;
- SA.GetSA();
- SA.prepare();
- for (int i = 1; i <= n; ++i) seg.Modify(seg.rt[i], seg.rt[i - 1], 1, n, SA.SA[i], 1);
- while (m--) {
- int A = read(),
- B = read(),
- C = read(),
- D = read();
- int ans = 0;
- int l = 0,
- r = min(B - A, D - C) + 1;
- while (l <= r) {
- int mid = (l + r) >> 1;
- if (SA.check(mid, A, B, C, D)) ans = mid,
- l = mid + 1;
- else r = mid - 1;
- }
- printf("%d\n", ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2506890.html