后缀数组总结（题目合集）

清疚 2024-04-17 05:56 8阅读 0赞

## 1、hdu6704 K-th occurrence（主席树+后缀树组） ##

## 题意：给定串s, q个询问(l,r,k)，求子串s\[l,r\]的第k次出现位置。 ##

## 分析：好题。考虑后缀树组sa的含义，sa数组将后缀排序之后，前缀最相似的必然放在了一起（相邻），如果sa\[x\]前后能找到和后缀x的最长公共前缀大于等于区间长度的后缀，那么说明有子串重复，我们在sa数组找到满足情况（lcp(i,x)>=len）的左右边界（l、r），如果r-l+1>=k，说明存在k个重复的子串，sa\[l\]-sa\[r\]存放就是他们出现的位置，第k大就是第k次出现的位置（首字符）。二分上下界要注意二分的姿势和细节，很容易出错。 ##

## 总结：被这个题目整了一天，对后缀树组的理解深入了不少，后缀树组还是很强大的，也复习了一下主席树，现在看来就是个模板题，对模板一定要熟悉，一定要用自己的，不然会吃大亏，以后都用这个题目的代码当模板了。 ##

## 代码： ##

#include <bits/stdc++.h>
    using namespace std;
    const int N=1e5+5;
    char s[N];
    int y[N],x[N],c[N],sa[N],rk[N],height[N];
    int t,n,m,q;
    
    /// -- 后缀树组模板部分 get_SA + get_height + bd_st() + rmq + qu_lcp 五个函数 --
    /// 字符串下标从1开始，因为主席树需要前缀和做差
    void get_SA() {
        memset(c,0,sizeof(c));
        for (int i=1; i<=n; ++i) ++c[x[i]=s[i]];
        for (int i=2; i<=m; ++i) c[i]+=c[i-1];
        for (int i=n; i>=1; --i) sa[c[x[i]]--]=i;
        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[x[i]];
            for (int i=2; i<=m; ++i) c[i]+=c[i-1];
            for (int i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
            swap(x,y);
            x[sa[1]]=1;
            num=1;
            for (int i=2; i<=n; ++i)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
            if (num==n) break;
            m=num;
        }
    }
    
    /// height数组 （height[i] 表示sa[i-1]和sa[i]的最长公共公共前缀）
    void get_height() {
        int k=0;
        for (int i=1; i<=n; ++i) rk[sa[i]]=i;
        for (int i=1; i<=n; ++i) {
            if (rk[i]==1) continue;
            if (k) --k;
            int j=sa[rk[i]-1];
            while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
            height[rk[i]]=k;
        }
    }
    
    /// st表  RMQ（height数组）
    int dp[N][20];
    void bd_st() {
        for (int i = 1; i <= n; i++) dp[i][0] = height[i];
        for (int j = 1; (1<<j) <= n; j++)
            for (int i = 1; i+(1<<j)-1 <= n; i++)
                dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
    }
    
    /// height[rank[l]+1] .... height[rank[r]] 的最小值（求lcp时使用）
    int rmq (int l, int r) {
        int k = 0;
        while ((1<<(k+1)) <= r-l+1) k++;
        return min(dp[l][k],dp[r-(1<<k)+1][k]);
    }
    
    /// 后缀x与后缀y的最长公共前缀
    int qu_lcp(int x, int y) {
        if(x == y) return n - x + 1;
        x = rk[x],y = rk[y];
        if(x > y) swap(x, y);
        return rmq(x+1,y);
    }
    
    /// 注意二分的细节 很容易出错
    int L,R;
    void get_inv(int x,int len) {
        /// 求满足lcp(i,rk[x])的起始端点最小的后缀
        int l=1,r=rk[x],mid;
        while(l<r) {
            mid = (l+r)/2;
            if(qu_lcp(x,sa[mid])>=len) r=mid;
            else l=mid+1;
        }
        L = l;
    
        /// 求满足lcp(i,rk[x])的起始端点最大的后缀
        l=rk[x],r=n;
        while(l<r) {
            mid = (l+r+1)/2;
            if(qu_lcp(x,sa[mid])>=len) l=mid;
            else r=mid-1;
        }
        R = l;
    }
    
    /// -- 主席树部分 --
    /// sa数组的值域为[1,n],可以不用离散化
    int a[N],b[N];
    int rt[N*20],ls[N*20],rs[N*20],sum[N*20],cnt=0;
    void up(int pre,int& o,int l,int r,int pos) {
    	o=++cnt;
    	ls[o]=ls[pre];
    	rs[o]=rs[pre];
    	sum[o]=sum[pre]+1;
    	if(l==r) return ;
    	int m=(l+r)/2;
    	if(pos<=m) up(ls[pre],ls[o],l,m,pos);
    	else up(rs[pre],rs[o],m+1,r,pos);
    }
    
    int qu(int pre,int o,int l,int r,int k) {
    	if(l==r) return l;///b[l];
    	int m=(l+r)/2;
    	if(sum[ls[o]]-sum[ls[pre]]>=k) return qu(ls[pre],ls[o],l,m,k);
    	else return qu(rs[pre],rs[o],m+1,r,k-(sum[ls[o]]-sum[ls[pre]]));
    }
    
    int main() {
        scanf("%d",&t);
        while(t--) {
            scanf("%d%d%s",&n,&q,s+1);
            m=130;///字符串最大ASCII码值
            get_SA();
            get_height();
            bd_st();
            /*
            for(int i=1;i<=n;i++) a[i]=b[i]=sa[i];
            sort(b+1,b+n+1);
            int sz=unique(b+1,b+1+n)-(b+1);
    		for(int i=1;i<=n;i++)
                a[i]=lower_bound(b+1,b+1+sz,a[i])-b;
            */
            cnt = 0;
            for(int i=1;i<=n;i++)
                up(rt[i-1],rt[i],1,n,sa[i]);
            while(q--) {
                int l,r,k;
                scanf("%d%d%d",&l,&r,&k);
                get_inv(l,r-l+1);
                if(R-L+1<k) printf("-1\n");
                else printf("%d\n",qu(rt[L-1],rt[R],1,n,k));
            }
        }
        return 0;
    }

## 2、Comet OJ - 2019国庆欢乐赛 字符串 ##

## 题意：[https://www.cometoj.com/contest/68/problem/G?problem\_id=3940][https_www.cometoj.com_contest_68_problem_G_problem_id_3940]。 ##

## 题解： ##

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][] ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e6+5;
    
    char s[N],t[N];
    int y[N],x[N],c[N],sa[N];
    int n,m=180;///n为字符串长度，m为最大字符ASCII码
    
    void get_SA() {
        memset(c,0,sizeof(c));
        for (int i=1; i<=n; ++i) ++c[x[i]=s[i]];
        for (int i=2; i<=m; ++i) c[i]+=c[i-1];
        for (int i=n; i>=1; --i) sa[c[x[i]]--]=i;
        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[x[i]];
            for (int i=2; i<=m; ++i) c[i]+=c[i-1];
            for (int i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
            swap(x,y);
            x[sa[1]]=1;
            num=1;
            for (int i=2; i<=n; ++i)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
            if (num==n) break;
            m=num;
        }
    }
    
    int q,bl[N],sz[N],ans[N];
    int main(){
        scanf("%d%s",&q,s+1);
        int len = strlen(s+1);
        int sl = len;
        s[++len] = 'z'+1;
        for(int i=1;i<=q;i++) {
            scanf("%s",t);
            int l = strlen(t);
            bl[len+1] = i;
            sz[i] = l;
            for(int j=0;j<l;j++)
                s[++len] = t[j];
            s[++len] = 'z'+2;
        }
        s[++len] = 'z'+2;
        n = len;
        get_SA();
        int mi = 1e9;
        for(int i=n;i>=1;i--) {
            if(sa[i]<=sl) mi = min(mi,sa[i]);
            else if(bl[sa[i]] && mi+sz[bl[sa[i]]]-1<=sl)
                ans[bl[sa[i]]] = mi;
        }
        for(int i=1;i<=q;i++) {
            if(ans[i]) printf("%d\n",ans[i]-1);
            else puts("-1");
        }
    	return 0;
    }

## 3、HDU 5008 Boring String Problem ##

## 题意：找到字符串中第k小（去重后）的子串，并且输出下标最小的那一个。 ##

## 分析：看到子串问题（子串排序）就想到是后缀数组问题，这题纯粹是后缀数组性质的综合运用。因为子串是后缀的前缀，后缀数组对后缀排序的同时，也对子串进行了排序。对于每一个sa\[i\],会产生不同的n - sa\[i\] - height\[i\]个子串，这些子串也是排好序的。可以二分求出这些子串中的第k小的子串所在的后缀。但是还需要找到一个出现最早的，也就是满足条件的最小的sa\[x\]。有一个显然的结论，二分找到的后缀一定是这个k小子串出现的最后一个位置，不然就不是sa\[i\]贡献的新子串了。（可以用反证法证明，举例也很容易想明白。）所以我们二分找到右端点，如何在sa数组满足条件区间\[l,r\]内RMQ求最小就是这个子串最开始出现的位置。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define inf 0x3f3f3f3f
    const int N = 1e6+5;
    char s[N];
    
    int y[N],x[N],c[N],sa[N],rk[N],height[N];
    int n,m;///n为字符串长度，m为最大字符ASCII码
    /// -- 后缀树组模板部分 get_SA + get_height + bd_st() + rmq + qu_lcp 五个函数 --
    /// 字符串下标从1开始，因为主席树需要前缀和做差
    void get_SA() {
        memset(c,0,sizeof(c));
        for (int i=1; i<=n; ++i) ++c[x[i]=s[i]];
        for (int i=2; i<=m; ++i) c[i]+=c[i-1];
        for (int i=n; i>=1; --i) sa[c[x[i]]--]=i;
        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[x[i]];
            for (int i=2; i<=m; ++i) c[i]+=c[i-1];
            for (int i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
            swap(x,y);
            x[sa[1]]=1;
            num=1;
            for (int i=2; i<=n; ++i)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
            if (num==n) break;
            m=num;
        }
    }
    
    /// height数组 （height[i] 表示sa[i-1]和sa[i]的最长公共公共前缀）
    void get_height() {
        int k=0;
        for (int i=1; i<=n; ++i) rk[sa[i]]=i;
        for (int i=1; i<=n; ++i) {
            if (rk[i]==1) continue;
            if (k) --k;
            int j=sa[rk[i]-1];
            while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
            height[rk[i]]=k;
        }
    }
    
    /// st表  RMQ（height数组）
    int dp[N][20],dp2[N][20];
    void bd_st() {
        for (int i = 1; i <= n; i++) dp[i][0] = height[i];
        for (int j = 1; (1<<j) <= n; j++)
            for (int i = 1; i+(1<<j)-1 <= n; i++)
                dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        for (int i = 1; i <= n; i++) dp2[i][0] = sa[i];
        for (int j = 1; (1<<j) <= n; j++)
            for (int i = 1; i+(1<<j)-1 <= n; i++)
                dp2[i][j] = min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
    }
    
    /// height[rank[l]+1] .... height[rank[r]] 的最小值（求lcp时使用）
    int rmq (int l, int r) {
        int k = 0;
        while ((1<<(k+1)) <= r-l+1) k++;
        return min(dp[l][k],dp[r-(1<<k)+1][k]);
    }
    
    int rmq2 (int l, int r) {
        int k = 0;
        while ((1<<(k+1)) <= r-l+1) k++;
        return min(dp2[l][k],dp2[r-(1<<k)+1][k]);
    }
    
    /// 后缀x与后缀y的最长公共前缀
    int qu_lcp(int x, int y) {
        if(x == y) return n - x + 1;
        x = rk[x],y = rk[y];
        if(x > y) swap(x, y);
        return rmq(x+1,y);
    }
    
    ll sum[N];
    int main(){
        int q;
        while(scanf("%s",s+1)!=EOF) {
            n = strlen(s+1);
            m = 180;
            get_SA();
            get_height();
            bd_st();
            for(int i=1;i<=n;i++)
                sum[i] = sum[i-1] + n - sa[i] + 1 - height[i];
            scanf("%d",&q);
            ll l = 0, r = 0, v, k;
            for(int i=1;i<=q;i++) {
                scanf("%lld",&v);
                k = (l^r^v) + 1;
                if(k > sum[n]) {
                    l = r = 0;
                    puts("0 0");
                    continue;
                }
                int L = 1,R = n, res = 0;
                while(L <= R) {
                    int mid = (L + R) / 2;
                    if(sum[mid] >= k) {
                        res = mid;
                        R = mid - 1;
                    }else L = mid + 1;
                }
                int len = height[res] + k - sum[res - 1];
                L = res , R = n;
                int ans = res;
                while(L <= R) {
                    int mid = (L + R) / 2;
                    if(qu_lcp(sa[res],sa[mid]) >= len) {
                        ans = mid;
                        L = mid + 1;
                    }else R = mid - 1;
                }
                l = rmq2(res,ans), r = l + len - 1;
                printf("%lld %lld\n",l,r);
            }
        }
    	return 0;
    }

[https_www.cometoj.com_contest_68_problem_G_problem_id_3940]: https://www.cometoj.com/contest/68/problem/G?problem_id=3940
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/2b834256fa5043d3a6e81c6e788d68df.png