gpt4 book ai didi

【学习笔记】字符串基础:后缀数组

转载 作者:撒哈拉 更新时间:2024-04-01 14:46:21 55 4
gpt4 key购买 nike

后置数组好难啊好难啊好难啊好难啊好难啊好难啊 。

最后还是听了不知道从 ftp 里搞出来的 yspm 讲课视频才听懂的,但是 yspm 用的屏幕绘画是看不见的比较尊贵,然后开了画图 。

本文约定字符串下标从 \(1\) 开始 。

后缀数组

后缀数组,即 \(\text{SA(Suffix Array)}\),主要关系到两个数组:

  • \(sa\) 。

    对于 \(sa_i\) 表示将所有后缀排序后第 \(i\) 小的后缀的编号,也就是排名为 \(i\) 的后缀的位置 。

    此处的排序是按照字典序排的 。

  • \(rk\) 。

    \(rk_i\) 表示从第 \(i\) 个位置开始的后缀的排名 。

两个数组满足以下性质 \(sa_{rk_{i}}=rk_{sa_{i}}=i\) 。

借用 \(\text{OI-wiki}\) 的一张图用于解释后缀数组内的 \(sa\) 和 \(rk\) 数组 。

求后缀数组

  • \(\text O(n^2\log n)\) 。

    最为暴力的想法 。

    直接大力 sort 排序,不难发现排序需要进行 \(\text O(n\log n)\) 次字符串比较,每次比较复杂度均为 \(\text O(n)\),所以是 \(\text O(n^2\log n)\)的 。

    这个很明显非常不优,肯定是不推荐的 。

  • \(\text O(n \log^2n)\) 。

    倍增做法 。

    首先对字符串 \(s\) 的所有长度为 \(1\) 的子串进行排序,得到排序后的编号数组 \(sa_1\) 和排名数组 \(rk_1\).

    用两个连起来的长度为 \(1\) 的子串作为排序的两个关键字(靠前的子串为第一关键字)进行排序,这样就可以获得长度为 \(2\) 的子串排序的结果 。

    然后我们再用两个长度为 \(2\) 的子串作为排序的两个关键字排序,以此类推,假设倍增后长度为 \(w\) 则当 \(i+w\) 加起来比 \(n\) 大的时候视 \(s_{i+w}\) 为无限小 。

    在最后我们倍增出来的长度已经大于等于 \(n\) 的时候就可以得到我们需要的后缀数组 \(sa\) 。

    显然倍增的过程是 \(\text O(\log n)\) ,而每次倍增用 sort 对子串进行排序是 \(\text O(n\log n)\) ,而每次子串的比较花费 \(2\) 次字符比较 。

    这个看起来就优多了,复杂度是 \(\text{O}(n \log^2 n)\) 的 。

    点击查看代码
    namespace SA{
        int sa[N],rk[N],oldrk[N];
        inline bool cmp(int x,int y,int w){
            return (rk[x]!=rk[y])?(rk[x+w]<rk[y+w]):(rk[x]<rk[y]);
        }
        inline void Init(char *s){
            int n=strlen(s+1);
            for_(i,1,n){
                sa[i]=i;
                rk[i]=s[i];
            }
            for(int w=1;w<n;w<<=1){
                sort(sa+1,sa+1+n,cmp);
                memcpy(oldrk,rk,sizeof(rk));
                int tot=0;
                for_(i,1,n){
                    if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])
                        rk[sa[i]]=tot;
                    else
                        rk[sa[i]]=++tot;
                }
            }
        }
    }
    using namespace SA;
    

    解释一下代码 。

    首先 cmp 是双关键字的,这是因为字典序排的没啥好说的 。

    为什么我们要复制一遍 rk 呢?(oldrk) 。

    这很明显是因为在计算同时也在修改 rk,原本的 rk 会被覆盖 。

    最后的判断是因为如果两个子串的字典序相同我们则需要去重 。

  • \(\text{ O}(n \log n)\) 。

    虽然上面那份代码已经可以通过 LOJ 的后缀排序,但我们还是认为 \(\text O(n \log^2 n)\) 不够优怎么办?发现主要瓶颈在于 \(\text O(n \log n)\) 的 sort 排序 。

    那么为什么不用线性的排序方法呢?计数排序,基数排序 。

    我们发现后缀数组的排序是双关键字,而且值域是排名也就是严格 \(\text O(n)\) 的 。

    所以可以使用基数排序来优化我们上面的倍增做法,这样我们就可以得到一份常数巨大的 \(\text O(n \log n)\) 做法 。

    常数巨大到连 \(\text O(n \log^2 n)\) 都跑不过,甚至很可能会T掉,因此我们需要常数优化 。

    • 第二关键字无需基数排序 。

      第二关键字排序的实质其实就是把超出字符串范围的 \(sa_i\) 放到 \(sa\) 数组头部,剩下的依原顺序放入 。

      因此我们完全可以直接完成而不是基数排序 。

    • 优化计数排序的值域 。

      我们在计算完 \(rk\) 只会就会留下一个 \(tot\),这个 \(tot\) 就是当前排序的值域,可以来跑基数排序而不再用 \(n\) 。

    这两个(尤其是第二个)优化非常显著,这样就可以跑过 \(\text O(n \log^2 n)\) 了,跑不过就是写假了,因为这样写常数会很小 。

    点击查看代码
    namespace SA{
        int sa[N],rk[N],oldrk[N],oldsa[N],w,cnt[N],key[N];
        inline bool cmp(int x,int y,int w){
            return (oldrk[x]==oldrk[y])&&(oldrk[x+w]==oldrk[y+w]);
        }
        inline void Init(char *s){
            int n=strlen(s+1),m=127,tot;
            for_(i,1,n) 
                rk[i]=s[i],
                ++cnt[rk[i]];
            for_(i,1,m) 
                cnt[i]+=cnt[i-1];
            _for(i,n,1) sa[cnt[rk[i]]--]=i;
            for(int w=1;;w<<=1,m=tot) {
                tot=0;
                _for(i,n,n-w+1) 
                    oldsa[++tot]=i;
                for_(i,1,n)
                    if(sa[i]>w) 
                        oldsa[++tot]=sa[i]-w;
                memset(cnt,0,sizeof(cnt));
                for_(i,1,n) 
                    ++cnt[key[i]=rk[oldsa[i]]];
                for_(i,1,m) 
                    cnt[i]+=cnt[i-1];
                _for(i,n,1) 
                    sa[cnt[key[i]]--]=oldsa[i];
                memcpy(oldrk+1,rk+1,n*sizeof(int));
                tot=0;
                for_(i,1,n)
                    rk[sa[i]]=((cmp(sa[i],sa[i-1],w))?(tot):(++tot));
                if(tot==n)
                    break;
            }
        }
    }
    using namespace SA;
    

    这里有一些可以卡常的点 。

    • 将 \(rk_{oldsa_i}\) 存下来,减少不连续内存访问 。

    • 用函数来计算是否重复减少不连续内存访问 。

  • \(\text O(n)\) 。

    一般是用不到的,\(\text O(n)\)做法虽然跑的比倍增要快但是空间和码量都巨大 。

    有两种做法,SA-IS 和 DC3,我都不会 。

\(\text{height}\) 数组

定义

首先我们要进行一些定义 。

  • 后缀\(i\) 。

    我们为了方便把从 \(i\) 开始的后缀称为后缀 \(i\) 。

  • \(\text{LCP}\)(最长公共前缀) 。

    \(\text{LCP}(x,y)\)是指字符串 \(x\) 与字符串 \(y\) 的最长公共前缀(的长度),在这里指后缀 \(x\) 与后缀 \(y\) 的最长公共前缀(的长度) 。

  • \(\text{height}\) 数组的定义 。

    \(height_i=\text {LCP}(sa_i,sa_{i-1})\) ,即第 \(i\) 名的后缀与它前一名(\(i-1\))的后缀的最长公共前缀 。

    注意这里是排名 。

    \(height_1=0\) 。

实现

实现 \(\text O(n)\) 求 \(\text{height}\) 数组需要一个引理 。

  • \(height_{rk_{i}}\ge height_{rk_{i-1}-1}\)

这个引理非常好啊,让人脑洞大开(物理) 。

下面是证明

image

当我们知道这个引理之后我们就可以暴力通过引理求 \(\text{height}\) 数组了 。

inline void Init_H(){
    int tot=0;
    for_(i,1,n){
        if(rk[i]==0) continue;
        if(tot) --tot;
        while(s[i+tot]==s[sa[rk[i]-1]+tot]) ++tot;
        height[rk[i]]=tot;
    }
}

\(k\) 不会超过 \(n\) ,因此最多减 \(n\) 次,所以最多也就只会加 \(2n\) 次 。

复杂度是严格 \(\text{O}(n)\) 的 。

应用&题目

后缀数组的应用非常多啊,我们一一列举 。

  • P3806 后缀排序 。

    这个是模板题,没啥好说的直接求即可 。

  • BZOJ5673 求可重叠最长重复子串 。

    最暴力的思路就是直接暴力比较子串和子串,复杂度 \(O(n^2)\) 。

    但是我们直接就发现实际上求得是 \(\text{height}\) 数组最大值 。

    因为BZOJ交不了所以我没写,口胡的思路 。

  • P4051「JSOI2007」字符加密 。

    都说是 \(\text{SA}\) 板子题,但是我一眼没看出来,菜 。

    哦我读假题了,这里其实是长度为 \(n\) 的一堆子串而不是全排序 。

    仔细看一看就可以发现其是一个环,然后把环直接大力展开,这样我们就得到了一个二倍长度的字符串 。

    然后我们就可以跑后缀数组了,求出 \(sa\) 之后直接大力判其后缀有没有第 \(n\) 个后缀即可,复杂度 \(\text O(n \log n)\) 完全可过 。

    • 核心代码 。

      inline void In(){
          scanf("%s",s+1);
          int len=strlen(s+1);
          for_(i,1,len) s[i+len]=s[i];
          Init(s);
          int newlen=strlen(s+1);
          for_(i,1,newlen){
              if(sa[i]+len>2*len) continue;
              putchar(s[sa[i]+len-1]);
          }
      }
      
  • P2463 Sandy 的卡片 。

    做的第一道不是板子的后缀数组题纪念 。

    先前后作差求出其差值也就是新的字符串,然后把所有串连接在一起,用后缀数组求出\(\text{LCP}\),然后二分长度,每次从头到尾扫一遍 。

    代码比较冗长 。

    • 核心代码 。

      inline void In(){
          n=read();
          for_(i,1,n){
              l[i]=read();
              for(int j=1;j<=l[i];++j){
                  a[i][j]=read();
                  if(j>1)mx=max(mx,a[i][j]-a[i][j-1]);
              }
              rt=min(rt,l[i]);
          }
          for(int i=1;i<=n;++i){
              for(int j=2;j<=l[i];++j){
                  b[++tot]=a[i][j]-a[i][j-1];
                  id[tot]=i;
              }
              b[++tot]=++mx;
          }
          for_(i,1,tot){
              mn=min(mn,b[i]);
          }
          for_(i,1,tot){
              b[i]=b[i]-mn+1;
              mx=max(mx,b[i]);
          }
          Init();
          Init_H();
          while(lt<=rt){
              if(check(mid=(lt+rt)>>1))
                  ans=mid+1,lt=mid+1;
              else rt=mid-1;
          }
          print(ans,"\n");
      }
      
  • P4248 「AHOI2013」差异 。

    这个题目看起来就非常板啊,首先我们发现前面两项其实是定值,为 \(\frac{n(n-1)(n+1)}{2}\),没啥好说的 。

    然后后面的 \(\text{LCP}\) 如何维护呢?

    在我对 \(\text{height}\) 数组引理证明时用了两个定理 。

    image

    这两个定理随便挑一个再肆意转化一下就能发现 \(\text{LCP}(i,j)\) 其实就是 \(min\{height[rk_i+1]\sim height[rk_j]\}\),然后这样就是一个非常经典的单调栈问题了 。

    • 核心代码 。

      inline void In(){
          scanf("%s",s+1);
          Init(s);
          Init_H(s);
          int n=strlen(s+1),ans=0;
          for_(i,1,n){
              while(height[STA[top]]>height[i]) --top;
              l[i]=i-STA[top];
              STA[++top]=i;
          }
          STA[++top]=n+1;
          height[n+1]=-1;
          _for(i,n,1){
              while(height[STA[top]]>=height[i])--top;
              ans-=2*height[i]*l[i]*(STA[top]-i);
              STA[++top]=i;
          }
          print(ans+n*(n-1)*(n+1)/2,"\n");
      }
      
  • P2336 「SCOI2012」猫星球上的点名 。

    一眼看过去似乎没什么思路,但是发现用AC自动机可以随便搞啊!但是这是后缀数组题单所以我要用后缀数组(悲 。

    发现\(n\)和\(m\)的范围很小,所以可以用一个非常暴力的思路来解决这个题 。

    先把所有串连起来跑一个后缀数组,然后对每一个询问向前、向后扫描并把答案放入set,set判重并输出size 。

    异常暴力的思路,还真能过 。

最后此篇关于【学习笔记】字符串基础:后缀数组的文章就讲到这里了,如果你想了解更多关于【学习笔记】字符串基础:后缀数组的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

55 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com