GabWiki

Appearance

字符串相关算法 ​

前缀函数与 KMP 算法 ​

前缀函数 ​

给定一个长度为 n 的字符串 s，其 前缀函数 被定义为一个长度为 n 的数组 π。 其中 π[i] 简单来说就是子串 s[0…i] 最长的相等的 真前缀 与 真后缀 的长度。

具体实现如下：

C++
// s为下标从0开始的字符串 其长度为n
int pi[N];
pi[0] = 0;
for (int i = 1; i < n; ++i) {
	int j = pi[i - 1];
	while (j > 0 && s[i] != s[j]) j = pi[j - 1];
	if (s[i] == s[j]) ++j;
	pi[i] = j;
}
// s为下标从0开始的字符串 其长度为n
int pi[N];
pi[0] = 0;
for (int i = 1; i < n; ++i) {
	int j = pi[i - 1];
	while (j > 0 && s[i] != s[j]) j = pi[j - 1];
	if (s[i] == s[j]) ++j;
	pi[i] = j;
}

时间复杂度：O(N)。

KMP 算法 ​

经典应用：【KMP算法, Rabin-Karp算法, 快速幂】找出字符串中第一个匹配项的下标

实现一：拼接字符串，前缀表，一次匹配 ​

详细说明见：在字符串中查找子串：Knuth–Morris–Pratt 算法

具体实现如下：

C++
// s为下标从0开始的文本串 其长度为n
// p为下标从0开始的模式串 其长度为m
char str[N + M];
int pi[N + M];
// 把字符串拼接为"p#s"的形式 其中#为一个既不在s中也不在t中出现的分隔符
strcpy(str, p);
str[m] = '#';
strcpy(str + m + 1, s);
// 求前缀函数 同时也是在匹配
for (int i = 1; i < m + 1 + n; ++i) {
	int j = pi[i - 1];
	while (j > 0 && str[i] != str[j]) j = pi[j - 1];
	if (str[i] == str[j]) ++j;
	pi[i] = j;
	if (i >= m + 1 && pi[i] == m) {
		// 匹配成功
	}
}
// s为下标从0开始的文本串 其长度为n
// p为下标从0开始的模式串 其长度为m
char str[N + M];
int pi[N + M];
// 把字符串拼接为"p#s"的形式 其中#为一个既不在s中也不在t中出现的分隔符
strcpy(str, p);
str[m] = '#';
strcpy(str + m + 1, s);
// 求前缀函数 同时也是在匹配
for (int i = 1; i < m + 1 + n; ++i) {
	int j = pi[i - 1];
	while (j > 0 && str[i] != str[j]) j = pi[j - 1];
	if (str[i] == str[j]) ++j;
	pi[i] = j;
	if (i >= m + 1 && pi[i] == m) {
		// 匹配成功
	}
}

时间复杂度：O(N+M)。

实现二：前缀表，两次匹配 ​

具体实现如下：

C++
// s为下标从0开始的文本串 其长度为n
// p为下标从0开始的模式串 其长度为m

// 求前缀表
int pi[M];
pi[0] = 0;
for (int i = 1, j = 0; i < m; ++i) {
	while (j > 0 && p[i] != p[j]) j = pi[j - 1];
	if (p[i] == p[j]) ++j;
	pi[i] = j;
}

// 匹配
for (int i = 0, j = 0; i < n; ++i) {
	while (j > 0 && s[i] != p[j]) j = pi[j - 1];
	if (s[i] == p[j]) ++j;
	if (j == m) {
		// 匹配成功
		j = pi[j - 1]; // 回退进行下一次匹配
	}
}
// s为下标从0开始的文本串 其长度为n
// p为下标从0开始的模式串 其长度为m

// 求前缀表
int pi[M];
pi[0] = 0;
for (int i = 1, j = 0; i < m; ++i) {
	while (j > 0 && p[i] != p[j]) j = pi[j - 1];
	if (p[i] == p[j]) ++j;
	pi[i] = j;
}

// 匹配
for (int i = 0, j = 0; i < n; ++i) {
	while (j > 0 && s[i] != p[j]) j = pi[j - 1];
	if (s[i] == p[j]) ++j;
	if (j == m) {
		// 匹配成功
		j = pi[j - 1]; // 回退进行下一次匹配
	}
}
C++
// s为下标从1开始的文本串 其长度为n
// p为下标从1开始的模式串 其长度为m

// 求前缀表
int pi[M];
pi[1] = 0;
for (int i = 2, j = 0; i <= m; ++i) {
	while (j > 0 && p[i] != p[j + 1]) j = pi[j];
	if (p[i] == p[j + 1]) ++j;
	pi[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; ++i) {
	while (j > 0 && s[i] != p[j + 1]) j = pi[j];
	if (s[i] == p[j + 1]) ++j;
	if (j == m) {
		// 匹配成功
		j = pi[j]; // 回退进行下一次匹配
	}
}
// s为下标从1开始的文本串 其长度为n
// p为下标从1开始的模式串 其长度为m

// 求前缀表
int pi[M];
pi[1] = 0;
for (int i = 2, j = 0; i <= m; ++i) {
	while (j > 0 && p[i] != p[j + 1]) j = pi[j];
	if (p[i] == p[j + 1]) ++j;
	pi[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; ++i) {
	while (j > 0 && s[i] != p[j + 1]) j = pi[j];
	if (s[i] == p[j + 1]) ++j;
	if (j == m) {
		// 匹配成功
		j = pi[j]; // 回退进行下一次匹配
	}
}
实现三：next 数组，两次匹配 ​

next 数组为原版前缀表右移一位，统一减一后得到的数组。

具体实现如下：

Java
// s为下标从1开始的文本串 其长度为n
// p为下标从1开始的模式串 其长度为m

// 求next数组
int[] ne = new int[m + 1];
for (int i = 2, j = 0; i <= m; ++i) {
	while (j > 0 && p[i] != p[j + 1]) j = ne[j]; // 前后缀不相同了 向前回退
	if (p[i] == p[j + 1]) ++j; // 找到相同的前后缀
	ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; ++i) {
	while (j > 0 && s[i] != p[j + 1]) j = ne[j];
	if (s[i] == p[j + 1]) ++j;
	if (j == m) {
		// 匹配成功
		j = ne[j]; // 回退进行下一次匹配
	}
}
// s为下标从1开始的文本串 其长度为n
// p为下标从1开始的模式串 其长度为m

// 求next数组
int[] ne = new int[m + 1];
for (int i = 2, j = 0; i <= m; ++i) {
	while (j > 0 && p[i] != p[j + 1]) j = ne[j]; // 前后缀不相同了 向前回退
	if (p[i] == p[j + 1]) ++j; // 找到相同的前后缀
	ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; ++i) {
	while (j > 0 && s[i] != p[j + 1]) j = ne[j];
	if (s[i] == p[j + 1]) ++j;
	if (j == m) {
		// 匹配成功
		j = ne[j]; // 回退进行下一次匹配
	}
}
C++
// s为下标从1开始的文本串 其长度为n
// p为下标从1开始的模式串 其长度为m

// 求next数组
int ne[M];
for (int i = 2, j = 0; i <= m; ++i) {
	while (j && p[i] != p[j + 1]) j = ne[j]; // 前后缀不相同了 向前回退
	if (p[i] == p[j + 1]) ++j; // 找到相同的前后缀
	ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; ++i) {
	while (j && s[i] != p[j + 1]) j = ne[j];
	if (s[i] == p[j + 1]) ++j;
	if (j == m) {
		// 匹配成功
		j = ne[j]; // 回退进行下一次匹配
	}
}
// s为下标从1开始的文本串 其长度为n
// p为下标从1开始的模式串 其长度为m

// 求next数组
int ne[M];
for (int i = 2, j = 0; i <= m; ++i) {
	while (j && p[i] != p[j + 1]) j = ne[j]; // 前后缀不相同了 向前回退
	if (p[i] == p[j + 1]) ++j; // 找到相同的前后缀
	ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; ++i) {
	while (j && s[i] != p[j + 1]) j = ne[j];
	if (s[i] == p[j + 1]) ++j;
	if (j == m) {
		// 匹配成功
		j = ne[j]; // 回退进行下一次匹配
	}
}

Trie ​

最基本的 Trie 数据结构 ​

模板题：Trie字符串统计

C++
// N为最大可能的节点数(最大可能的字符串总长度)  K为字符串中可能出现的字符种类数
int sons[N][K], cnt[N], idx;

void insert(char word[]) {
    int p = 0;
    for (int i = 0; word[i]; ++i) {
        int curr = word[i] - 'a';
        if (!sons[p][curr]) sons[p][curr] = ++idx;
        p = sons[p][curr];
    }
    ++cnts[p];
}

int count(char word[]) {
    int p = 0;
    for (int i = 0; word[i]; ++i) {
        int curr = word[i] - 'a';
        if (!sons[p][curr]) return 0;
        p = sons[p][curr];
    }
    return cnts[p];
}
// N为最大可能的节点数(最大可能的字符串总长度)  K为字符串中可能出现的字符种类数
int sons[N][K], cnt[N], idx;

void insert(char word[]) {
    int p = 0;
    for (int i = 0; word[i]; ++i) {
        int curr = word[i] - 'a';
        if (!sons[p][curr]) sons[p][curr] = ++idx;
        p = sons[p][curr];
    }
    ++cnts[p];
}

int count(char word[]) {
    int p = 0;
    for (int i = 0; word[i]; ++i) {
        int curr = word[i] - 'a';
        if (!sons[p][curr]) return 0;
        p = sons[p][curr];
    }
    return cnts[p];
}

可持久化 Trie ​

先放个 P4735 最大异或和 的实现代码在这，待更新...

C++
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 6e5 + 10, K = log2(1e7) + 1;
int n, m;
int s[N];
char op[2];
int sons[N * K][2], vers[N * K], roots[N], idx;

void insert(int u, int p, int v) {
    vers[u] = v;
    for (int i = K - 1; i >= 0; --i) {
        int d = (s[v] >> i) & 1;
        sons[u][!d] = sons[p][!d];
        sons[u][d] = ++idx;
        u = sons[u][d], p = sons[p][d];
        vers[u] = v;
    }
}

int query(int x, int u, int l) {
    int res = 0;
    for (int i = K - 1; i >= 0; --i) {
        int d = (x >> i) & 1;
        if (vers[sons[u][!d]] >= l) res |= (1 << i), u = sons[u][!d];
        else u = sons[u][d];
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    vers[0] = -1;
    roots[0] = ++idx;
    insert(roots[0], 0, 0);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
        s[i] ^= s[i - 1];
        roots[i] = ++idx;
        insert(roots[i], roots[i - 1], i);
    }
    while (m--) {
        scanf("%s", op);
        if (op[0] == 'A') {
            scanf("%d", &s[++n]);
            s[n] ^= s[n - 1];
            roots[n] = ++idx;
            insert(roots[n], roots[n - 1], n);
        } else {
            int l, r, x; scanf("%d%d%d", &l, &r, &x);
            int ans = query(s[n] ^ x, roots[r - 1], l - 1);
            printf("%d\n", ans);
        }
    }

    return 0;
}
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 6e5 + 10, K = log2(1e7) + 1;
int n, m;
int s[N];
char op[2];
int sons[N * K][2], vers[N * K], roots[N], idx;

void insert(int u, int p, int v) {
    vers[u] = v;
    for (int i = K - 1; i >= 0; --i) {
        int d = (s[v] >> i) & 1;
        sons[u][!d] = sons[p][!d];
        sons[u][d] = ++idx;
        u = sons[u][d], p = sons[p][d];
        vers[u] = v;
    }
}

int query(int x, int u, int l) {
    int res = 0;
    for (int i = K - 1; i >= 0; --i) {
        int d = (x >> i) & 1;
        if (vers[sons[u][!d]] >= l) res |= (1 << i), u = sons[u][!d];
        else u = sons[u][d];
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    vers[0] = -1;
    roots[0] = ++idx;
    insert(roots[0], 0, 0);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
        s[i] ^= s[i - 1];
        roots[i] = ++idx;
        insert(roots[i], roots[i - 1], i);
    }
    while (m--) {
        scanf("%s", op);
        if (op[0] == 'A') {
            scanf("%d", &s[++n]);
            s[n] ^= s[n - 1];
            roots[n] = ++idx;
            insert(roots[n], roots[n - 1], n);
        } else {
            int l, r, x; scanf("%d%d%d", &l, &r, &x);
            int ans = query(s[n] ^ x, roots[r - 1], l - 1);
            printf("%d\n", ans);
        }
    }

    return 0;
}

AC 自动机 ​

AC 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的自动机，用于解决多模式匹配等任务。

C++
// N为最大可能的节点数(最大可能的字符串总长度)  K为字符串中可能出现的字符种类数
// fail[v]表示节点v在失配时回跳边的指向的节点
// sons[u][i]表示节点u的树边或转移边指向的节点
int sons[N][K], cnts[N], idx, fail[N];

// 与Trie一样的插入
void insert(char* s) {
    int p = 0;
    for (int k = 0; s[k]; ++k) {
        int i = s[k] - 'a';
        if (!sons[p][i]) sons[p][i] = ++idx;
        p = sons[p][i];
    }
    ++cnts[p];
}

// 建立转移边和回跳边
void build() {
    queue<int> que;
    for (int i = 0; i < K; ++i) {
        if (sons[0][i]) que.push(sons[0][i]);
    }
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = 0; i < K; ++i) {
            int v = sons[u][i];
			// 当子节点存在时 为子节点建立回跳边: 指向父节点的回跳边所指节点的子节点
            if (v) fail[v] = sons[fail[u]][i], que.push(v);
			// 当子节点不存在时 为当前节点建立转移边: 指向当前节点的回跳边所指节点的子节点
            else sons[u][i] = sons[fail[u]][i];
        }
    }
}

int query(char* s) {
    int res = 0;
	// u指针走主串对应节点 沿着树边/转移边走 保证不回退
    for (int k = 0, u = 0; s[k]; ++k) {
        u = sons[u][s[k] - 'a'];
		// v指针沿着回跳边搜索模式串 每次从当前节点(u)走到根节点
        for (int v = u; v && ~cnts[v]; v = fail[v]) {
			// 如果模式串只算一次匹配就要置空cnts[v]和对cnts[v]做条件判断
            res += cnts[v], cnts[v] = -1;
        }
    }
    return res;
}
// N为最大可能的节点数(最大可能的字符串总长度)  K为字符串中可能出现的字符种类数
// fail[v]表示节点v在失配时回跳边的指向的节点
// sons[u][i]表示节点u的树边或转移边指向的节点
int sons[N][K], cnts[N], idx, fail[N];

// 与Trie一样的插入
void insert(char* s) {
    int p = 0;
    for (int k = 0; s[k]; ++k) {
        int i = s[k] - 'a';
        if (!sons[p][i]) sons[p][i] = ++idx;
        p = sons[p][i];
    }
    ++cnts[p];
}

// 建立转移边和回跳边
void build() {
    queue<int> que;
    for (int i = 0; i < K; ++i) {
        if (sons[0][i]) que.push(sons[0][i]);
    }
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = 0; i < K; ++i) {
            int v = sons[u][i];
			// 当子节点存在时 为子节点建立回跳边: 指向父节点的回跳边所指节点的子节点
            if (v) fail[v] = sons[fail[u]][i], que.push(v);
			// 当子节点不存在时 为当前节点建立转移边: 指向当前节点的回跳边所指节点的子节点
            else sons[u][i] = sons[fail[u]][i];
        }
    }
}

int query(char* s) {
    int res = 0;
	// u指针走主串对应节点 沿着树边/转移边走 保证不回退
    for (int k = 0, u = 0; s[k]; ++k) {
        u = sons[u][s[k] - 'a'];
		// v指针沿着回跳边搜索模式串 每次从当前节点(u)走到根节点
        for (int v = u; v && ~cnts[v]; v = fail[v]) {
			// 如果模式串只算一次匹配就要置空cnts[v]和对cnts[v]做条件判断
            res += cnts[v], cnts[v] = -1;
        }
    }
    return res;
}

后缀数组 ​

后缀数组（Suffix Array）主要关系到两个数组：sa 和 rk。

其中：

  • sa[i] 表示将所有后缀排序后第 i 小的后缀的编号，也是所说的后缀数组；
  • rk[i] 表示后缀 i 的排名，是重要的辅助数组。

简单来说，sa[i] 表示排名为 i 的是哪个后缀，rk[i] 表示第 i 个后缀的秩（排名）是多少。

这两个数组满足性质：sa[rk[i]]=rk[sa[i]]=i。

O(Nlog2⁡N) 的做法 ​

递增+快排。

代码中加了两个常数优化（代码中高亮部分）：

  1. 单独提出 dup() 函数来计算是否重复：减少不连续内存访问（在数据范围较大时优化效果比较明显）；
  2. 若排名都不相同可直接生成后缀数组：考虑新的 rk 数组，若其值域为 [1,n] 那么每个排名都不同，此时无需再排序。
C++
// 字符串长度为n 序列输入至s[1...n]
char s[N];
// 为了防止访问rk[sa[i]+w]与rk_bak[sa[i]+w]导致数组越界 开两倍数组
int sa[N], rk[N], rk_bak[N * 2];

bool dup(const int& x, const int& y, const int& w) {
	return rk_bak[x] == rk_bak[y] && rk_bak[x + w] == rk_bak[y + w];
}

int n = strlen(s + 1);
for (int i = 1; i <= n; ++i) sa[i] = i, rk[i] = s[i];
for (int w = 1; w < n; w <<= 1) {
	sort(sa + 1, sa + n + 1, [&](const int& x, const int& y) {
		return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];
	});
	memcpy(rk_bak + 1, rk + 1, n * sizeof(int));
	int p = 0;
	for (int i = 1; i <= n; ++i) {
		rk[sa[i]] = dup(sa[i], sa[i - 1], w) ? p : ++p;
	}
	if (p == n) break;
}
// 字符串长度为n 序列输入至s[1...n]
char s[N];
// 为了防止访问rk[sa[i]+w]与rk_bak[sa[i]+w]导致数组越界 开两倍数组
int sa[N], rk[N], rk_bak[N * 2];

bool dup(const int& x, const int& y, const int& w) {
	return rk_bak[x] == rk_bak[y] && rk_bak[x + w] == rk_bak[y + w];
}

int n = strlen(s + 1);
for (int i = 1; i <= n; ++i) sa[i] = i, rk[i] = s[i];
for (int w = 1; w < n; w <<= 1) {
	sort(sa + 1, sa + n + 1, [&](const int& x, const int& y) {
		return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];
	});
	memcpy(rk_bak + 1, rk + 1, n * sizeof(int));
	int p = 0;
	for (int i = 1; i <= n; ++i) {
		rk[sa[i]] = dup(sa[i], sa[i - 1], w) ? p : ++p;
	}
	if (p == n) break;
}

O(Nlog⁡N) 的做法 ​

递增+计排。

更易理解的版本的代码中加了三个常数优化（代码中高亮部分）：

  1. 单独提出 dup() 函数来计算是否重复：减少不连续内存访问（在数据范围较大时优化效果比较明显）；
  2. 若排名都不相同可直接生成后缀数组：考虑新的 rk 数组，若其值域为 [1,n] 那么每个排名都不同，此时无需再排序；
  3. 优化计数排序的值域：每次对 rk 进行更新之后，我们都计算了一个 p，这个 p 即是 rk 的值域，将值域改成它即可。

常数更小的版本的代码在上面的基础上多加了两个常数优化（代码中高亮部分）：

  1. 第二关键字无需计数排序；
  • 第二关键字排序的实质，其实就是把超出字符串范围（即 sa[i]+w>n）的 sa[i] 放到 sa 数组头部，然后把剩下的依原顺序放入。
C++
int idx = 0;
for (int i = n; i > n - w; --i) sk[++idx] = i;
for (int i = 1; i<= n; ++i) {
   if (sa[i] > w) sk[++idx] = sa[i] - w;
}
int idx = 0;
for (int i = n; i > n - w; --i) sk[++idx] = i;
for (int i = 1; i<= n; ++i) {
   if (sa[i] > w) sk[++idx] = sa[i] - w;
}
  • 先把第二关键字为无穷小的位置放前面，再把剩下的按排好的顺序放进去。
  1. 将 rk[sk[i]] 存下来：减少不连续内存访问（在数据范围较大时优化效果非常明显）；
C++
// 字符串长度为n 序列输入至s[1...n]
char s[N];
// 为了防止访问rk[sa[i]+w]与rk_bak[sa[i]+w]导致数组越界 开两倍数组
int sa[N], rk[N * 2], sa_bak[N], rk_bak[N * 2], cnts[N];

bool dup(const int& x, const int& y, const int& w) {
    return rk_bak[x] == rk_bak[y] && rk_bak[x + w] == rk_bak[y + w];
}

int n = strlen(s + 1), m = 128;
// 计排
for (int i = 1; i <= n; ++i) ++cnts[rk[i] = s[i]];
for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
for (int i = n; i >= 1; --i) sa[cnts[rk[i]]--] = i;
// 更新rk
memcpy(rk_bak + 1, rk + 1, n * sizeof(int));
for (int p = 0, i = 1; i <= n; ++i) {
	rk[sa[i]] = dup(sa[i], sa[i - 1], 0) ? p : ++p;
}
for (int w = 1; w < n; w <<= 1) {
	// 对第二关键字sa[i]+w进行计排
	memset(cnts, 0, (m + 1) * sizeof(int));
	memcpy(sa_bak + 1, sa + 1, n * sizeof(int));
	for (int i = 1; i <= n; ++i) ++cnts[rk[sa_bak[i] + w]];
	for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
	for (int i = n; i >= 1; --i) sa[cnts[rk[sa_bak[i] + w]]--] = sa_bak[i];
	// 对第一关键字sa[i]进行计排
	memset(cnts, 0, (m + 1) * sizeof(int));
	memcpy(sa_bak + 1, sa + 1, n * sizeof(int));
	for (int i = 1; i <= n; ++i) ++cnts[rk[sa_bak[i]]];
	for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
	for (int i = n; i >= 1; --i) sa[cnts[rk[sa_bak[i]]]--] = sa_bak[i];
	// 更新rk
	memcpy(rk_bak + 1, rk + 1, n * sizeof(int));
	int p = 0;
	for (int i = 1; i <= n; ++i) {
		rk[sa[i]] = dup(sa[i], sa[i - 1], w) ? p : ++p;
	}
	if (p == n) break;
	m = p;
}
// 字符串长度为n 序列输入至s[1...n]
char s[N];
// 为了防止访问rk[sa[i]+w]与rk_bak[sa[i]+w]导致数组越界 开两倍数组
int sa[N], rk[N * 2], sa_bak[N], rk_bak[N * 2], cnts[N];

bool dup(const int& x, const int& y, const int& w) {
    return rk_bak[x] == rk_bak[y] && rk_bak[x + w] == rk_bak[y + w];
}

int n = strlen(s + 1), m = 128;
// 计排
for (int i = 1; i <= n; ++i) ++cnts[rk[i] = s[i]];
for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
for (int i = n; i >= 1; --i) sa[cnts[rk[i]]--] = i;
// 更新rk
memcpy(rk_bak + 1, rk + 1, n * sizeof(int));
for (int p = 0, i = 1; i <= n; ++i) {
	rk[sa[i]] = dup(sa[i], sa[i - 1], 0) ? p : ++p;
}
for (int w = 1; w < n; w <<= 1) {
	// 对第二关键字sa[i]+w进行计排
	memset(cnts, 0, (m + 1) * sizeof(int));
	memcpy(sa_bak + 1, sa + 1, n * sizeof(int));
	for (int i = 1; i <= n; ++i) ++cnts[rk[sa_bak[i] + w]];
	for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
	for (int i = n; i >= 1; --i) sa[cnts[rk[sa_bak[i] + w]]--] = sa_bak[i];
	// 对第一关键字sa[i]进行计排
	memset(cnts, 0, (m + 1) * sizeof(int));
	memcpy(sa_bak + 1, sa + 1, n * sizeof(int));
	for (int i = 1; i <= n; ++i) ++cnts[rk[sa_bak[i]]];
	for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
	for (int i = n; i >= 1; --i) sa[cnts[rk[sa_bak[i]]]--] = sa_bak[i];
	// 更新rk
	memcpy(rk_bak + 1, rk + 1, n * sizeof(int));
	int p = 0;
	for (int i = 1; i <= n; ++i) {
		rk[sa[i]] = dup(sa[i], sa[i - 1], w) ? p : ++p;
	}
	if (p == n) break;
	m = p;
}
C++
// 字符串长度为n 序列输入至s[1...n]
char s[N];
// 为了防止访问rk[sa[i]+w]与rk_bak[sa[i]+w]导致数组越界 开两倍数组
// pk表示第一关键字(Primary Keyword) sk表示第二关键字(Secondary Keyword)
int sa[N], rk[N], rk_bak[N * 2], cnts[N], pk[N], sk[N];

bool dup(const int& x, const int& y, const int& w) {
    return rk_bak[x] == rk_bak[y] && rk_bak[x + w] == rk_bak[y + w];
}

int n = strlen(s + 1), m = 128;
// 计排
for (int i = 1; i <= n; ++i) ++cnts[rk[i] = s[i]];
for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
for (int i = n; i >= 1; --i) sa[cnts[rk[i]]--] = i;
for (int w = 1; w < n; w <<= 1) {
	// 根据性质优化第二关键字排序
	int idx = 0;
	for (int i = n; i > n - w; --i) sk[++idx] = i;
	for (int i = 1; i<= n; ++i) {
		if (sa[i] > w) sk[++idx] = sa[i] - w;
	}
	// 对第一关键字sa[i]进行计排
	memset(cnts, 0, (m + 1) * sizeof(int));
	for (int i = 1; i <= n; ++i) ++cnts[pk[i] = rk[sk[i]]];
	for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
	for (int i = n; i >= 1; --i) sa[cnts[pk[i]]--] = sk[i];
	// 更新rk
	memcpy(rk_bak + 1, rk + 1, n * sizeof(int));
	int p = 0;
	for (int i = 1; i <= n; ++i) {
		rk[sa[i]] = dup(sa[i], sa[i - 1], w) ? p : ++p;
	}
	if (p == n) break;
	m = p;
}
// 字符串长度为n 序列输入至s[1...n]
char s[N];
// 为了防止访问rk[sa[i]+w]与rk_bak[sa[i]+w]导致数组越界 开两倍数组
// pk表示第一关键字(Primary Keyword) sk表示第二关键字(Secondary Keyword)
int sa[N], rk[N], rk_bak[N * 2], cnts[N], pk[N], sk[N];

bool dup(const int& x, const int& y, const int& w) {
    return rk_bak[x] == rk_bak[y] && rk_bak[x + w] == rk_bak[y + w];
}

int n = strlen(s + 1), m = 128;
// 计排
for (int i = 1; i <= n; ++i) ++cnts[rk[i] = s[i]];
for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
for (int i = n; i >= 1; --i) sa[cnts[rk[i]]--] = i;
for (int w = 1; w < n; w <<= 1) {
	// 根据性质优化第二关键字排序
	int idx = 0;
	for (int i = n; i > n - w; --i) sk[++idx] = i;
	for (int i = 1; i<= n; ++i) {
		if (sa[i] > w) sk[++idx] = sa[i] - w;
	}
	// 对第一关键字sa[i]进行计排
	memset(cnts, 0, (m + 1) * sizeof(int));
	for (int i = 1; i <= n; ++i) ++cnts[pk[i] = rk[sk[i]]];
	for (int i = 1; i <= m; ++i) cnts[i] += cnts[i - 1];
	for (int i = n; i >= 1; --i) sa[cnts[pk[i]]--] = sk[i];
	// 更新rk
	memcpy(rk_bak + 1, rk + 1, n * sizeof(int));
	int p = 0;
	for (int i = 1; i <= n; ++i) {
		rk[sa[i]] = dup(sa[i], sa[i - 1], w) ? p : ++p;
	}
	if (p == n) break;
	m = p;
}