Kasai 算法
Kasai 算法用于根据给定的后缀数组和文本构建最长公共前缀（也称为 LCP）数组。构建 LCP 数组后，我们就可以高效地在给定文本中搜索模式。我们已经讨论了几种可以高效解决模式匹配问题的算法，包括 KMP 算法、Boyer-Moore 算法和 Rabin-Karp 算法。在本教程中，我们将探索 Kasai 算法。
Kasai 算法的工作原理？
要理解 Kasai 算法，我们首先需要学习该算法的两个核心概念 −
后缀数组 −这是一个按字典顺序存储给定文本中所有后缀的起始索引的数组。
LCP 数组 − 顾名思义，它是两个字符串的最长公共前缀（简称 LCP），即同时包含这两个字符串的最长前缀。
Kasai 算法基于以下观察 −
如果从位置 i 和 j 开始的两个后缀的 LCP 为 k，则从 i+1 和 j+1 开始的后缀的 LCP 至少为 k-1，除非其中一个是后缀数组中的最后一个后缀。这是因为，在删除第一个字符后，后缀中字符的相对顺序保持不变，除非它们到达文本末尾。因此，我们可以利用此属性，在后缀数组的线性扫描中计算 LCP 值，从第一个后缀开始，并在变量 k 中跟踪当前的 LCP 值。
每当我们移动到下一个后缀对时，我们将 k 减 1，然后只要 i+k 和 j+k 位置上的字符匹配，就将其加 1。为了找到下一个后缀对，我们使用一个逆数组，将每个后缀索引映射到其在后缀数组中的位置。
让我们考虑一下 Kasai 算法 − 的输入输出场景。
输入： 字符串："AABAAABCEDBABCDDEBC" 输出： 后缀数组：0 1 9 3 8 2 14 10 4 11 5 15 7 12 13 6 常用前缀数组：1 2 3 0 4 1 2 2 0 1 1 1 1 0 1 0
示例
以下示例实际演示了不同编程语言中的 Kasai 算法。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
// Defining a structure to represent suffix
struct suffixes {
int index;
int rank[2];
};
// 比较两个后缀的函数
int compare(const void* a, const void* b) {
struct suffixes* suf1 = (struct suffixes*)a;
struct suffixes* suf2 = (struct suffixes*)b;
// 如果第一名的排名相同
if(suf1->rank[0] == suf2->rank[0]) {
// 比较第二名
return (suf1->rank[1] < suf2->rank[1]) ? -1 : 1;
}else {
return (suf1->rank[0] < suf2->rank[0]) ? -1 : 1;
}
}
// 构建后缀数组的函数
int* createSuffArray(char* orgnlString, int n) {
struct suffixes suffArray[n];
for (int i = 0; i < n; i++) {
suffArray[i].index = i;
// 根据角色本身排名
suffArray[i].rank[0] = orgnlString[i] - 'a';
// 下一个等级是下一个角色
suffArray[i].rank[1] = ((i+1)<n)?(orgnlString[i+1]-'a'):-1;
}
// 对后缀进行排序
qsort(suffArray, n, sizeof(struct suffixes), compare);
int index[n];
for (int k = 4; k < 2*n; k = k*2) {
int currRank = 0;
int prevRank = suffArray[0].rank[0];
suffArray[0].rank[0] = currRank;
index[suffArray[0].index] = 0;
// 为第一个后缀分配等级和索引值
for (int i = 1; i < n; i++) {
if (suffArray[i].rank[0] == prevRank && suffArray[i].rank[1] == suffArray[i-1].rank[1]) {
prevRank = suffArray[i].rank[0];
// 如果与之前的排名相同，则分配相同的新排名
suffArray[i].rank[0] = currRank;
} else{
prevRank = suffArray[i].rank[0];
// 增加排名并分配
suffArray[i].rank[0] = ++currRank;
}
index[suffArray[i].index] = i;
}
for (int i = 0; i < n; i++) {
int nextIndex = suffArray[i].index + k/2;
suffArray[i].rank[1] = (nextIndex < n)? suffArray[index[nextIndex]].rank[0]: -1;
}
qsort(suffArray, n, sizeof(struct suffixes), compare);
}
// to 存储所有已排序后缀的索引
int* suffixVector = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
suffixVector[i] = suffArray[i].index;
return suffixVector;
}
// 应用Kasai算法构建LCP阵列
int* kasaiAlgorithm(char* orgnlString, int* suffixVector, int n) {
// 存储 lcp 数组
int* longPrefix = (int*)malloc(n * sizeof(int));
// 存储后缀数组元素的逆
int* suffixInverse = (int*)malloc(n * sizeof(int));
// 填充 suffixInverse[] 数组中的值
for (int i=0; i < n; i++)
suffixInverse[suffixVector[i]] = i;
int k = 0;
for (int i=0; i<n; i++) {
if (suffixInverse[i] == n-1) {
k = 0;
continue;
}
int j = suffixVector[suffixInverse[i]+1];
while (i+k<n && j+k<n && orgnlString[i+k]==orgnlString[j+k])
k++;
longPrefix[suffixInverse[i]] = k;
if (k>0)
k--;
}
return longPrefix;
}
void displayArray(int* vec, int n) {
for (int i = 0; i < n; i++)
printf("%d ", vec[i]);
printf("
");
}
int main() {
char orgnlString[] = "AAABCAEAAABCBDDAAAABC";
int n = strlen(orgnlString);
int* suffArray = createSuffArray(orgnlString, n);
printf("Suffix Array is:
");
displayArray(suffArray, n);
// 调用函数构建LCP数组
int* prefixCommn = kasaiAlgorithm(orgnlString, suffArray, n);
// 打印 LCP 阵列
printf("Common Prefix Array is:
");
displayArray(prefixCommn, n);
return 0;
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// Defining a structure to represent suffix
struct suffixes {
int index;
int rank[2];
};
// 比较两个后缀的函数
bool compare(suffixes suf1, suffixes suf2) {
// 如果第一名的排名相同
if(suf1.rank[0] == suf2.rank[0]) {
// 比较第二名
if(suf1.rank[1] < suf2.rank[1])
return true;
else
return false;
}else {
if(suf1.rank[0] < suf2.rank[0])
return true;
else
return false;
}
}
// 构建后缀数组的函数
vector<int> createSuffArray(string orgnlString) {
int n = orgnlString.size();
suffixes suffArray[n];
for (int i = 0; i < n; i++) {
suffArray[i].index = i;
// 根据角色本身排名
suffArray[i].rank[0] = orgnlString[i] - 'a';
// 下一个等级是下一个角色
suffArray[i].rank[1] = ((i+1)<n)?(orgnlString[i+1]-'a'):-1;
}
// 对后缀进行排序
sort(suffArray, suffArray+n, compare);
int index[n];
for (int k = 4; k < 2*n; k = k*2) {
int currRank = 0;
int prevRank = suffArray[0].rank[0];
suffArray[0].rank[0] = currRank;
index[suffArray[0].index] = 0;
// 为第一个后缀分配等级和索引值
for (int i = 1; i < n; i++) {
if (suffArray[i].rank[0] == prevRank && suffArray[i].rank[1] == suffArray[i-1].rank[1]) {
prevRank = suffArray[i].rank[0];
// 如果与之前的排名相同，则分配相同的新排名
suffArray[i].rank[0] = currRank;
} else{
prevRank = suffArray[i].rank[0];
// 增加排名并分配
suffArray[i].rank[0] = ++currRank;
}
index[suffArray[i].index] = i;
}
for (int i = 0; i < n; i++) {
int nextIndex = suffArray[i].index + k/2;
suffArray[i].rank[1] = (nextIndex < n)? suffArray[index[nextIndex]].rank[0]: -1;
}
sort(suffArray, suffArray+n, compare);
}
// to 存储所有已排序后缀的索引
vector<int>suffixVector;
for (int i = 0; i < n; i++)
suffixVector.push_back(suffArray[i].index);
return suffixVector;
}
// 应用Kasai算法构建LCP阵列
vector<int> kasaiAlgorithm(string orgnlString, vector<int> suffixVector) {
int n = suffixVector.size();
// 存储 lcp 数组
vector<int> longPrefix(n, 0);
// 存储后缀数组元素的逆
vector<int> suffixInverse(n, 0);
// 填充 suffixInverse[] 数组中的值
for (int i=0; i < n; i++)
suffixInverse[suffixVector[i]] = i;
int k = 0;
for (int i=0; i<n; i++) {
if (suffixInverse[i] == n-1) {
k = 0;
continue;
}
int j = suffixVector[suffixInverse[i]+1];
while (i+k<n && j+k<n && orgnlString[i+k]==orgnlString[j+k])
k++;
longPrefix[suffixInverse[i]] = k;
if (k>0)
k--;
}
return longPrefix;
}
void displayArray(vector<int> vec) {
vector<int>::iterator it;
for (it = vec.begin(); it < vec.end() ; it++)
cout << *it << " ";
cout << endl;
}
int main() {
string orgnlString = "AAABCAEAAABCBDDAAAABC";
vector<int>suffArray = createSuffArray(orgnlString);
int n = suffArray.size();
cout<< "Suffix Array is: "<<endl;
displayArray(suffArray);
// 调用函数构建LCP数组
vector<int>prefixCommn = kasaiAlgorithm(orgnlString, suffArray);
// 打印 LCP 阵列
cout<< "Common Prefix Array is: "<<endl;
displayArray(prefixCommn);
}
import java.util.Arrays;
public class Main {
// 定义一个类来表示后缀
static class suffixes {
int index;
int[] rank = new int[2];
}
// 比较两个后缀的方法
static int compare(suffixes suf1, suffixes suf2) {
// 如果第一名的排名相同
if (suf1.rank[0] == suf2.rank[0]) {
// 比较第二名
if (suf1.rank[1] < suf2.rank[1])
return -1;
else
return 1;
} else {
if (suf1.rank[0] < suf2.rank[0])
return -1;
else
return 1;
}
}
// 构建后缀数组的方法
static int[] createSuffArray(String orgnlString) {
int n = orgnlString.length();
suffixes[] suffArray = new suffixes[n];
for (int i = 0; i < n; i++) {
suffArray[i] = new suffixes();
suffArray[i].index = i;
// 根据角色本身排名
suffArray[i].rank[0] = orgnlString.charAt(i) - 'a';
// 下一个等级是下一个角色
suffArray[i].rank[1] = ((i + 1) < n) ? (orgnlString.charAt(i + 1) - 'a') : -1;
}
// 对后缀进行排序
Arrays.sort(suffArray, Main::compare);
int[] index = new int[n];
for (int k = 4; k < 2 * n; k = k * 2) {
int currRank = 0;
int prevRank = suffArray[0].rank[0];
suffArray[0].rank[0] = currRank;
index[suffArray[0].index] = 0;
// 为第一个后缀分配等级和索引值
for (int i = 1; i < n; i++) {
if (suffArray[i].rank[0] == prevRank && suffArray[i].rank[1] == suffArray[i - 1].rank[1]) {
prevRank = suffArray[i].rank[0];
// 如果与之前的排名相同，则分配相同的新排名
suffArray[i].rank[0] = currRank;
} else {
prevRank = suffArray[i].rank[0];
// 增加排名并分配
suffArray[i].rank[0] = ++currRank;
}
index[suffArray[i].index] = i;
}
for (int i = 0; i < n; i++) {
int nextIndex = suffArray[i].index + k / 2;
suffArray[i].rank[1] = (nextIndex < n) ? suffArray[index[nextIndex]].rank[0] : -1;
}
Arrays.sort(suffArray, Main::compare);
}
// to 存储所有已排序后缀的索引
int[] suffixVector = new int[n];
for (int i = 0; i < n; i++)
suffixVector[i] = suffArray[i].index;
return suffixVector;
}
// 应用Kasai算法构建LCP阵列
static int[] kasaiAlgorithm(String orgnlString, int[] suffixVector) {
int n = suffixVector.length;
// 存储 lcp 数组
int[] longPrefix = new int[n];
// 存储后缀数组元素的逆
int[] suffixInverse = new int[n];
// 填充 suffixInverse[] 数组中的值
for (int i = 0; i < n; i++)
suffixInverse[suffixVector[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) {
if (suffixInverse[i] == n - 1) {
k = 0;
continue;
}
int j = suffixVector[suffixInverse[i] + 1];
while (i + k < n && j + k < n && orgnlString.charAt(i + k) == orgnlString.charAt(j + k))
k++;
longPrefix[suffixInverse[i]] = k;
if (k > 0)
k--;
}
return longPrefix;
}
static void displayArray(int[] vec) {
for (int i : vec)
System.out.print(i + " ");
System.out.println();
}
public static void main(String[] args) {
String orgnlString = "AAABCAEAAABCBDDAAAABC";
int[] suffArray = createSuffArray(orgnlString);
System.out.println("Suffix Array is: ");
displayArray(suffArray);
// 调用方法构建LCP数组
int[] prefixCommn = kasaiAlgorithm(orgnlString, suffArray);
// 打印 LCP 阵列
System.out.println("Common Prefix Array is: ");
displayArray(prefixCommn);
}
}
# 定义一个类来表示后缀
class Suffix:
def __init__(self):
self.index = 0
self.rank = [0, 0]
# 比较两个后缀的函数
def compare(a, b):
if a.rank[0] == b.rank[0]:
if a.rank[1] < b.rank[1]:
return -1
else:
return 1
else:
if a.rank[0] < b.rank[0]:
return -1
else:
return 1
# 构建后缀数组的函数
def createSuffArray(orgnlString):
n = len(orgnlString)
suffArray = [Suffix() for _ in range(n)]
for i in range(n):
suffArray[i].index = i
suffArray[i].rank[0] = ord(orgnlString[i]) - ord('a')
suffArray[i].rank[1] = ord(orgnlString[i + 1]) - ord('a') if ((i + 1) < n) else -1
suffArray = sorted(suffArray, key=lambda x: (x.rank[0], x.rank[1]))
ind = [0]*n
k = 4
while k < 2*n:
rank = 0
prev_rank = suffArray[0].rank[0]
suffArray[0].rank[0] = rank
ind[suffArray[0].index] = 0
for i in range(1, n):
if suffArray[i].rank[0] == prev_rank and suffArray[i].rank[1] == suffArray[i - 1].rank[1]:
prev_rank = suffArray[i].rank[0]
suffArray[i].rank[0] = rank
else:
prev_rank = suffArray[i].rank[0]
rank += 1
suffArray[i].rank[0] = rank
ind[suffArray[i].index] = i
for i in range(n):
nextIndex = suffArray[i].index + k//2
suffArray[i].rank[1] = suffArray[ind[nextIndex]].rank[0] if (nextIndex < n) else -1
suffArray = sorted(suffArray, key=lambda x: (x.rank[0], x.rank[1]))
k *= 2
suffixVector = [0]*n
for i in range(n):
suffixVector[i] = suffArray[i].index
return suffixVector
# 应用Kasai算法构建LCP阵列
def kasaiAlgorithm(orgnlString, suffixVector):
n = len(suffixVector)
longPrefix = [0]*n
suffixInverse = [0]*n
for i in range(n):
suffixInverse[suffixVector[i]] = i
k = 0
for i in range(n):
if suffixInverse[i] == n - 1:
k = 0
continue
j = suffixVector[suffixInverse[i] + 1]
while i + k < n and j + k < n and orgnlString[i + k] == orgnlString[j + k]:
k += 1
longPrefix[suffixInverse[i]] = k
if k > 0:
k -= 1
return longPrefix
# 打印数组的函数
def displayArray(vec):
for i in vec:
print(i, end=' ')
print()
def main():
orgnlString = "AAABCAEAAABCBDDAAAABC"
suffArray = createSuffArray(orgnlString)
print("Suffix Array is: ")
displayArray(suffArray)
prefixCommn = kasaiAlgorithm(orgnlString, suffArray)
print("Common Prefix Array is: ")
displayArray(prefixCommn)
if __name__ == "__main__":
main()
输出
后缀数组为： 15 0 7 16 17 1 8 2 9 18 5 19 3 10 12 4 11 20 14 13 6 常用前缀数组为： 3 5 5 2 4 4 4 3 3 3 0 2 2 2 0 1 1 1 1 0 0
