P3809

【模板】后缀排序

就是求字符串后缀数组的模板。

采用倍增法求后缀数组。

首先我们有一个长度为 1 的后缀前缀的排序。

然后我们将长度翻倍，将后面一半的后缀前缀作为第二关键字，前面一半的后缀前缀作为第一关键字，排序就可以得到新的后缀数组。

然后我们采取基数排序的方法，优化每次排序的复杂度。

具体地，先按照第二关键字排序，存入 $id$ 数组，然后以 $id$ 为顺序基础采用计数排序排出第一关键字得到此时的 $sa$ 数组。

然后中间有过程用到了 $sa(rk(i))=rk(sa(i))=i$ 这样的小性质。

最后时间复杂度就是 $O(n\log n)$ 的。

然后这个东西显然常数巨大。

所以需要一些卡常。

首先将第二关键字排序的结果直接转移。

然后记录一个 $p$ 把需要计数排序的值域缩小。每次求出 $sa$ 数组后把重复的归到一个排名里，于是就能缩小 $rk$ 的值域。

还有几个可能优化效率不是那么高的。

首先是另外使用一个 $px$ 数组记录 $rk(id(i))$ 减少不连续内存访问。

针对值域缩小的过程，可以用一个 $cmp$ 函数使最后比较时访问的不连续内存减少。

最后还可以在值域为 $[1,n]$ 的时候直接退出（因为每个排名都是唯一的，不用再排序了）。

这样就可以过了。。。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e6;

ll n,m;
ll sa[N+5],rk[N*2+5],oldrk[N*2+5],id[N+5],cnt[N+5],px[N+5];
char s[N+5];

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline bool cmp(ll x,ll y,ll w) {
  return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
}

int main() {
  
  scanf("%s",s+1);n=strlen(s+1);m=max(n,300ll);
  
  for(ll i=1;i<=n;i++) ++cnt[rk[i]=s[i]];
  for(ll i=1;i<=m;i++) cnt[i]+=cnt[i-1];
  for(ll i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;
  
  for(ll w=1,p=0;;w<<=1,m=p) {
    p=0;for(ll i=n;i>n-w;i--) id[++p]=i;
    for(ll i=1;i<=n;i++) {if(sa[i]>w) id[++p]=sa[i]-w;}
    memset(cnt,0,sizeof(cnt));
    for(ll i=1;i<=n;i++) ++cnt[px[i]=rk[id[i]]];
    for(ll i=1;i<=m;i++) cnt[i]+=cnt[i-1];
    for(ll i=n;i>=1;i--) sa[cnt[px[i]]--]=id[i];
    memcpy(oldrk,rk,sizeof(rk));
    p=0;for(ll i=1;i<=n;i++) {rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;}
    if(p==n) {for(ll i=1;i<=n;i++) sa[rk[i]]=i;break;}
  }
  
  for(ll i=1;i<=n;i++) {write(sa[i]);putchar(' ');}
  
  return 0;
}

后缀数组应用：

1. 寻找最小的循环移动位置：

   将字符串 $S$ 复制变成 $SS$ 后后缀排序即可。

   例题：P4051 [JSOI2007]字符加密

2. 字符串在线查找子串：

   因为已经将后缀排序，子串的实质是后缀的前缀，所以直接二分即可。

   对于出现次数，因为这个东西在后缀数组上是连续的，找到首尾就可以计算出现次数了（输出出现的位置就更不用说了）。

3. 从字符串首位取字符最小化字典序：

   例题：P2870 [USACO07DEC]Best Cow Line G

   实际上需要比较正串和反串的大小。

   想办法用上后缀排序。一个好方法就是把字符串翻转之后接上原来的字符串，然后比较就可以了。

   接上的时候中间加入一个串中不会出现的字符。

---

height 数组

定义 $LCP ( i , j )$ 为后缀 $i$ 和后缀 $j$ 的最长公共前缀（的长度）。

定义 $height(i) = LCP ( sa (i) , sa ( i - 1 ))$。特别地，$height ( 1 ) = 0$。

引理：$height ( rk (i) ) \ge height ( rk (i-1) ) - 1$。

因此求 $height(i)$ 实际上根据上面那个引理暴力即可。

应用：

1. 两子串最长公共前缀：

   $LCP( sa ( i ) , sa ( j ) ) = \min _ { k \in [ i+1 , j ]} \{ height( k ) \}$

   感性理解就是后缀是经过排序的，如果说差距不大的后缀那自然没什么差距，如果说直接变掉某个字符的话那就根本不可能变回来了，自然就是取这些 $height$ 的最小值作答案。

   有了这个，求两子串最长公共前缀就变成了 RMQ 问题。

2. 比较一个字符串的两个子串的大小关系：

   假设要比较的是 $A = S [ a \cdots b ]$ 和 $B = S [ c \cdots d]$ 的大小关系。

   若 $ LCP ( a , c ) \ge \min \{ |A| , |B| \}$，那么 $ |A| < |B| \Leftrightarrow A < B$。

   否则，就是直接用排名数组比较：$rk (a) < rk (c) \Leftrightarrow A < B$。

3. 不同子串的数目：

   计算串的总数，再减掉重复。

   至于重复的是哪一部分？当然是 $height$ 数组的和。

   所以最后的答案就是：$ n(n+1)/2 - \sum _ { i = 2 } ^ { n } height (i)$。

4. 出现至少 $k$ 次的子串的最大长度：

   实际上就是在 $height$ 数组上的滑动窗口，单调队列即可。

   例题：P2852 [USACO06DEC]Milk Patterns G

5. 在文本串中至少不重叠地出现了两次的字符串的最大长度：

   二分目标串的长度 $|s|$，然后把 $height$ 数组中长度 $\ge |s|$ 的连续段拿出来。

   然后 RMQ 求出每个段内最大和最小的下标（原串中的，具体地，如果 $height$ 数组的下标为 $[l,r]$，那么就是求 $sa$ 在 $[l-1 , r]$ 上的最值）。

   如果距离大于等于 $|s|$，说明存在满足条件的字符串。

6. 连续的若干相同子串：

   内容咕咕咕（IOI2009 集训队论文罗穗骞 P20~21）。

   例题：P1117 [NOI2016] 优秀的拆分

   • 有一个 $O( n^2 )$ 的 Hash 做法。
   • 在这个 Hash 的基础上，枚举长度 $|s|$ 对字符串进行分块，后缀数组预处理 LCP 和 LCS 的查询，
   • 答案数组的维护最好差分（线段树可能常数略大）

7. 结合并查集：

   例题：P2178 [NOI2015] 品酒大会

8. 结合线段树：咕。

9. 结合单调栈：咕。

   例题一：P4248 [AHOI2013]差异

   例题二：P3181 [HAOI2016]找相同字符