Content #
拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，那就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，就记录
prefix[k]=true。
把 suffix 数组和 prefix 数组的计算过程，用代码实现出来，就是下面这个样子：
// b表示模式串，m表示长度，suffix，prefix数组事先申请好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
for (int i = 0; i < m; ++i) { // 初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i) { // b[0, i]
int j = i;
int k = 0; // 公共后缀子串长度
while (j >= 0 && b[j] == b[m-1-k]) { // 与b[0, m-1]求公共后缀子串
--j;
++k;
suffix[k] = j+1; //j+1表示公共后缀子串在b[0, i]中的起始下标
}
if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
}
}
Viewpoints #
From #
33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？