后缀数组

后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也并不逊色。

后缀数组

• 两种做法
  • 倍增
    • O(nlogn)
  • CD3
    • O(n)
• 要点
  • 下标从1开始
• 后缀例子
  • aababb
    • aababb
    • ababb
    • babb
    • abb
    • bb
    • b
• 详细解答
• sa[c[x[y[i]]]]
  • 首先说明x[i]: i的排名; y[i]: 排名是i。为什么计数排序倒着排序呢？实际上是为了保证排序稳定性，那么我们可以默认排序前的位置为第二关键字此时可以看作y[i]=i，于是之前排序的过程是sa[c[x[i]]]其实最里面的i可以看做y[i] ，如法炮制即可。
  • x[] 是第一关键词的“排名”， y[]是第二关键词的”排序“。在基数排序中，先枚举的数会排后面。在SA的双关键词基数排序中，我们是做了x[]的桶，为了保证第一关键词相同情况下第二关键词从小到大排序，我们得先枚举第二关键词大的数，而y[]则提供了这种排序。所以有sa[c[x[y[i]]]]。
• 主要数组
  • sa[i]
    • 排名第i位的是第几个后缀
  • rk[i]
    • 第i个后缀的排名是多少
  • height[i]
    • sa[i]和sa[i-1]的最长公共前缀
    • 简要求法
      • height[i]=lcp(i-1,j)
  • h(i)
    • 第i个后缀和排名在它前面一位的后缀这两个后缀之间的最长公共前缀的长度
    • h(i)=height[rk[i]]
    • 性质
      • h(i)≥h(i-1)-1
    • k=h(i-1)≥h(i-2)-1
  • k
    • 变化
      • 减n次
        • -n→+n
• 关键字
• lcp
  • lcp(i,j)概念
    • 排名第i位的后缀和第j位的后缀的最长公共前缀
  • 公式
    • lcp(i,j)=lcp(j,i)
      • 和i,j顺序无关
    • lcp(i,i)=len(i)
      • 第i个后缀的长度
    • lcp(i,j)=min(lcp(i,k),lcp(k,j))
      • 原为≥，由夹逼定理得=
      • 证明
      • 引申
        • lcp(i,j)=min(lcp(i,i+1),lcp(i+1,i+2)……lcp(j-1,j)
• 作用
  • 将所有后缀按字典序排序
• i<j,i>j即交换,i≤k≤j
• 夹逼定理：函数A>B,函数B>C，函数A的极限是X，函数C的极限也是X ，那么函数B的极限就一定是X，这个就是夹逼定理。
• 证明：k+1个后缀一定排在第i个后缀的上面且它们的最长公共前缀等于这两个公共前缀去掉第一个字母因为他们只有第一个字母不同