2024年4月11日发(作者：羊尔柳)
sa函数的表达式
sa函数是一种字符串算法，全称为“Suffix Array”，即后缀数组。它
是一种对字符串进行快速排序的数据结构，用于解决字符串相关问题，
如最长公共子串、模式匹配等。
sa函数的表达式如下：
sa(string s, int n, int m) {
for (int i = 1; i <= n; i++) {
rk[i] = s[i];
cnt[rk[i]]++;
}
for (int i = 2; i <= m; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = n; i >= 1; i--) {
sa[cnt[rk[i]]--] = i;
}
for (int k = 1; k <= n; k <<= 1) {
int num = 0;
for (int i = n - k + 1; i <= n; i++) {
tmp[++num] = i;
}
for (int i = 1; i <= n; i++) {
if (sa[i] > k) {
tmp[++num] = sa[i] - k;
}
}
for (int i = 0; i <= m; i++) {
cnt[i] = 0;
}
for (int i = 1; i <= n; i++) {
cnt[rk[tmp[i]]]++;
}
for (int i = 2; i <= m; ++i) {
cnt[i] += cnt[i - 1];
}
for (int j = n; j >= 1 ; j--) {
sa[cnt[rk[tmp[j]]]--] = tmp[j];
}
swap(rk, tmp);
rk[sa[1]] = 1;
num = 1;
for (int i = 2; i <= n; i++) {
if (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + k] ==
tmp[sa[i - 1] + k]) {
rk[sa[i]] = num;
} else {
rk[sa[i]] = ++num;
}
}
if (num == n) {
break;
}
m = num;
}
}
其中，s为输入的字符串，n为字符串的长度，m为字符集大小。rk
数组表示字符串中每个字符的排名，cnt数组表示每个字符出现的次数，
sa数组表示后缀数组，tmp数组用于排序时的临时存储。
该函数的主要思路是利用桶排实现对字符串的排序。首先将每个字符
看作一个单独的后缀，并按照其字典序进行排序。然后将相邻两个后
缀合并成一个新的后缀，并再次进行排序。重复以上步骤直到所有后
缀都被合并成一个。
在实现过程中，需要注意以下几点：
1. 排序时需要考虑到相同前缀的情况，因此需要使用倍增法实现。
2. 在合并相邻两个后缀时，需要保证新生成的后缀仍然是按照字典序
排列。
3. 在计算rk数组时，需要考虑到相同后缀的情况。
4. 在每次排序后需要更新rk数组和sa数组。
5. 在最后一次排序时，如果所有后缀都已经合并成一个，则可以直接
退出循环。
总之，sa函数是一种高效的字符串算法，在解决字符串相关问题时具
有重要的应用价值。对于程序员来说，了解sa函数的表达式及其实现
原理是非常有益的。
2024年4月11日发(作者：羊尔柳)
sa函数的表达式
sa函数是一种字符串算法，全称为“Suffix Array”，即后缀数组。它
是一种对字符串进行快速排序的数据结构，用于解决字符串相关问题，
如最长公共子串、模式匹配等。
sa函数的表达式如下：
sa(string s, int n, int m) {
for (int i = 1; i <= n; i++) {
rk[i] = s[i];
cnt[rk[i]]++;
}
for (int i = 2; i <= m; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = n; i >= 1; i--) {
sa[cnt[rk[i]]--] = i;
}
for (int k = 1; k <= n; k <<= 1) {
int num = 0;
for (int i = n - k + 1; i <= n; i++) {
tmp[++num] = i;
}
for (int i = 1; i <= n; i++) {
if (sa[i] > k) {
tmp[++num] = sa[i] - k;
}
}
for (int i = 0; i <= m; i++) {
cnt[i] = 0;
}
for (int i = 1; i <= n; i++) {
cnt[rk[tmp[i]]]++;
}
for (int i = 2; i <= m; ++i) {
cnt[i] += cnt[i - 1];
}
for (int j = n; j >= 1 ; j--) {
sa[cnt[rk[tmp[j]]]--] = tmp[j];
}
swap(rk, tmp);
rk[sa[1]] = 1;
num = 1;
for (int i = 2; i <= n; i++) {
if (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + k] ==
tmp[sa[i - 1] + k]) {
rk[sa[i]] = num;
} else {
rk[sa[i]] = ++num;
}
}
if (num == n) {
break;
}
m = num;
}
}
其中，s为输入的字符串，n为字符串的长度，m为字符集大小。rk
数组表示字符串中每个字符的排名，cnt数组表示每个字符出现的次数，
sa数组表示后缀数组，tmp数组用于排序时的临时存储。
该函数的主要思路是利用桶排实现对字符串的排序。首先将每个字符
看作一个单独的后缀，并按照其字典序进行排序。然后将相邻两个后
缀合并成一个新的后缀，并再次进行排序。重复以上步骤直到所有后
缀都被合并成一个。
在实现过程中，需要注意以下几点：
1. 排序时需要考虑到相同前缀的情况，因此需要使用倍增法实现。
2. 在合并相邻两个后缀时，需要保证新生成的后缀仍然是按照字典序
排列。
3. 在计算rk数组时，需要考虑到相同后缀的情况。
4. 在每次排序后需要更新rk数组和sa数组。
5. 在最后一次排序时，如果所有后缀都已经合并成一个，则可以直接
退出循环。
总之，sa函数是一种高效的字符串算法，在解决字符串相关问题时具
有重要的应用价值。对于程序员来说，了解sa函数的表达式及其实现
原理是非常有益的。