字符串-KMP算法
若干个字符组成字符串
字符串前缀prefix, 真前缀proper prefix, 后缀suffix, 真后缀proper suffix
串匹配算法
查找一个模式串(pattern)在文本串(text)中的位置
经典的串匹配算法
- 蛮力 Brute Force
- KMP
- Boyer-Moore
- Karp-Rabin
- Sunday
蛮力算法
以字符为单位, 从左到右移动模式串, 直到匹配成功
蛮力1
pi 的取值范围[0, plen)
ti 的取值范围[0, tlen)
pi = 0
ti -= pi - 1
当pi == plen 时, 成功匹配
public static int index(String text, String pattern) {
// 检测合法性
if (text == null || pattern == null) return -1;
char [] textChars = text.toCharArray();
int tlen = textChars.length;
char [] patternChars = pattern.toCharArray();
int plen = patternChars.length;
if (tlen == 0 || plen == 0 || tlen < plen) return -1;
int pi = 0, ti = 0;
while (pi < plen && ti < tlen) {
if (textChars[ti] == patternChars[pi]) {
ti++;
pi++;
} else {
ti = ti - pi + 1;
pi = 0;
}
}
return pi == plen ? ti - pi : -1;
}
优化
在后几位匹配成功后, 长度超出字符串的范围, 提前退出
ti 的退出条件为
- ti - pi <= tlen - plen
- ti - pi, 是指每一轮比较中text 的首个比较字符的位置
/**
* 改进
* @param text
* @param pattern
* @return
*/
public static int index2(String text, String pattern) {
// 检测合法性
if (text == null || pattern == null) return -1;
char [] textChars = text.toCharArray();
int tlen = textChars.length;
char [] patternChars = pattern.toCharArray();
int plen = patternChars.length;
if (tlen == 0 || plen == 0 || tlen < plen) return -1;
int pi = 0, ti = 0;
while (pi < plen && ti - pi < tlen - plen) {
if (textChars[ti] == patternChars[pi]) {
ti++;
pi++;
} else {
ti = ti - pi + 1;
pi = 0;
}
}
return pi == plen ? ti - pi : -1;
}
蛮力2
pi 的取值范围[0, plen)
ti 的取值范围[0, tlen - plen)
pi = 0
ti++
pi == plen 时, 成功匹配
public static int index(String text, String pattern) {
// 检测合法性
if (text == null || pattern == null) return -1;
char [] textChars = text.toCharArray();
int tlen = textChars.length;
char [] patternChars = pattern.toCharArray();
int plen = patternChars.length;
if (tlen == 0 || plen == 0 || tlen < plen) return -1;
int tiMax = tlen = plen;
for (int ti = 0; ti < tiMax; ti++) {
int pi = 0;
for (; pi < plen; pi++) {
if (textChars[ti + pi] != patternChars[pi]) break;
}
if (pi == plen) return ti;
}
return -1;
}
蛮力性能分析
n 是文本串长度, m 是模式串长度
最多n - m + 1 轮比较
最好的情况下
- 只需一轮比较, 匹配成功, 比较m 次, 时间复杂度O(m)
最坏情况下
- 执行n - m + 1 轮比价
- 每轮都比较至模式串的末字符后失败, m - 1 次成功, 1 次失败
- 时间复杂度为O(m*(n-m+1)), 由于一般m 远小于n, 所以O(mn)
KMP
预先根据模式串内容生成一张next 表
比较字符不等时, 在next 表中找到之前模式串的最大公共子串长度
原理:
- 当d, e 失配, 如果pattern 能够一次性向右移动一大段距离, 比较d 和c 字符
- A 和B 相等
- 所以KMP 必须在失配字符e 左边的子串中找出符合条件的AB, 从而得知向右移动的距离
- 向右移动的距离: e 左边子串长度 - A 的长度 == e 的索引 - c 的索引, 且c 的索引 == next[e的索引], 所以向右移动距离: e 的索引 - next[e的索引]
总结
- 如果在pi 位置失配, 向右移动的距离是pi - next[pi], 所以next[pi] 越小, 移动距离越大
- next[pi] 是pi 左边子串真前缀后缀的最大公共子串长度
向右移动一位得到next 表
public static int indexOf(String text, String pattern) {
// 检测合法性
if (text == null || pattern == null) return -1;
char [] textChars = text.toCharArray();
int tlen = textChars.length;
char [] patternChars = pattern.toCharArray();
int plen = patternChars.length;
if (tlen == 0 || plen == 0 || tlen < plen) return -1;
// 得到next 表
int[] next = next(pattern);
int pi = 0, ti = 0;
while (pi < plen && ti < tlen) {
// next 第一个位置置为-1, 当pi == -1, 则pi = 0, ti++, 相当于模式串向后移动一位
if (pi < 0 || textChars[ti] == patternChars[pi]) {
ti++;
pi++;
} else {
pi = next[pi];
}
}
return pi == plen ? ti - pi : -1;
}
为什么是最大公共子串长度
- 将3 赋值pi, 向右移动1 个字符单位, 最后成功匹配
- 将1 赋值pi, 向右移动3 个字符单位, 错过错过匹配机会
公共子串长度越小, 向右移动距离越大, 越不安全
公共子串长度越大, 向右移动距离越小, 越安全
构造思路
next[i] == n
- 如果pattern.charAt(i) == pattern.charAt(n)
- 则next[i + 1] == n + 1
- 如果pattern.charAt(i) != pattern.charAt(n)
- 已知next[n] == k
- 如果pattern.charAt(i) == pattern.charAt(k)
- 则next[i + 1] == k + 1
- 如果pattern.charAt(i) != pattern.charAt(k)
- 将k 带入n, 重复执行这个比较2
private static int[] next2(String pattern) {
char[] chars = pattern.toCharArray();
int[] next = new int[chars.length];
next[0] = -1;
int i = 0;
int n = -1;
int iMax = chars.length - 1;
while (i < iMax) {
if (n < 0 || chars[i] == chars[n]) {
next[++i] = ++n;
} else {
n = next[n];
}
}
return next;
}
不足, 如果遇到相同字符的内容, 则不必要比较
优化思路
next[i] == n, next[n] == k
如果pattern[i] != d, 就让模式串滑动到next[i], n 的位置, 跟d 进行比较
如果pattern[n] != d, 就让模式串滑动到next[n], k 的位置, 跟d 进行比较
如果pattern[i] == pattern[n], 那么当i 位置失配, 模式串最终必然滑动到k 位置跟d 进行比较
所以, next[i] 直接存储next[n] 即可
private static int[] next(String pattern) {
char[] chars = pattern.toCharArray();
int[] next = new int[chars.length];
next[0] = -1;
int i = 0;
int n = -1;
int iMax = chars.length - 1;
while (i < iMax) {
if (n < 0 || chars[i] == chars[n]) {
++i;
++n;
if (chars[i] == chars[n]) {
next[i] = next[n];
} else {
next[i] = n;
}
} else {
n = next[n];
}
}
return next;
}
性能分析
KMP 主要逻辑
最好时间复杂度O(m)
最坏时间复杂度O(n), 不超过O(2n)
next 表构造过程跟kmp 主体逻辑类似, 时间复杂度O(m)
所以得到整体
最好时间复杂度O(m)
最坏时间复杂度O(n + m)
空间复杂度O(m)
BM
Boyer-Moore, 简称BM
- 最坏时间复杂度O(n/m), 最坏为O(n + m)
- 从模式串的尾部开始匹配
2 条计算规则计算出最大值
- 坏字符规则(Bad Character, BC)
- 好后缀规则(Good Suffix, GS)
坏字符规则
当pattern 中的字符E 和text 中的S 失配时, 称S 为坏字符
- 如果pattern 的未匹配子串中不存在坏字符, 直接将pattern移动到坏字符的下一位
- 否则, 让pattern 的未匹配子串中最靠右的坏字符与text 中的坏字符对齐
好后缀规则
MPLE 是一个成功匹配的后缀, E, LE, PLE, MPLE 都是好后缀
- 如果pattern 中找不到与好后缀对齐的子串, 直接将pattern 移动到好后缀的下一位
- 否则, 从pattern 中找出子串与text 中的好后缀对齐
BM 分析
最好情况, 时间复杂度O(n/m)
最坏情况, 时间复杂度O(n + m), 其中O(m) 为构造表的时间
Sunday
思路和BM 类似
从前向后匹配
-
当失配时, 关注的是text 中参与匹配的正常的下一位字符A
如果A 没有在pattern 中出现, 则直接跳过, 即 移动位数 = pattern + 1
否则, 让pattern 中最靠右的A 与text 中的A 对齐
