SA 后缀数组 / SAM 后缀自动机 c++ 模板

前言

SA 后缀数组模板 SAM 后缀自动机模板

代码 1.SA

#include 
#include 
using namespace std;
const int maxn = 1e6 + 6;
char s[maxn];
int rk[maxn], sa[maxn], height[maxn];
int sa2[maxn], oldrk[maxn], tank[maxn];
int n, m;
bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
void rsort() {  // sa2为基数排序而构造
  for (int i = 1; i