1.0 问题描述
实现KMP算法查找字符串。
2.0 问题分析
- “KMP算法”是对字符串查找“简单算法”的优化。
- 字符串查找“简单算法”是源字符串每个字符分别使用匹配串进行匹配，一旦失配，模式串下标归0，源字符串下标加1。
- 可以很容易计算字符串查找“简单算法”的时间复杂度为O（m*n），其中n表示源字符串长度，m表示匹配串长度。
- KMP算法的匹配方式同简单算法的匹配方式相同，只不过在失配的时候，模式串下标不归零，反而会根据模式串自身的重复信息，回归到一个大于0的下标。从而减少匹配次数。
- 那么失配时候，模式串下标回归的位置需要提前计算好。计算的方法是，匹配串中，每个位置的前缀字符串“头部”和“尾部”的重复字符数即为失配下标回归位置。
- 假设匹配串是：ababc
- 下标0的字符是“a”，它的前缀是空字符串，所以回归位置为0
- 下标1的字符是“b”，它的前缀是“a”，数量不足2个，回归位置也是0
- 下标2的字符是“a”，他的前缀是“ab”，没有重复的头部和尾部，回归位置是0
- 下标3的字符是“b”，它的前缀是“aba”，有重复的头部和尾部，重复子串是“a”，长度为1，回归位置是1
- 下标3的字符是“c”，它的前缀是“abab”，有重复的头部和尾部，重复子串是“ab”，长度为2，回归位置是2
- 根据上一条，我们可以计算出一个next数组用于保存失配时模式串下标应该回到哪里的下标序列。
- 计算好next数组后，就可以使用“简单算法”的逻辑进行匹配了，只不过不同的是，一旦失配，匹配串下标不是回归到0，而是根据next数组决定。
3.0 代码实现
3.1使用swift实现
///简单查找
func simpleSearch(_ src: String, _ mode: String, _ start: Int) -> Int {
var i = start;
while i < src.count {
var j = 0;
while j < mode.count {
if(i + j >= src.count || src[i + j] != mode[j]){
break;
}
j += 1;
}
if j == mode.count{
return i;
}
i += 1;
}
return -1;
}
///kmp字符串查找
func kmpSearch(_ src: String, _ mode: String, _ start: Int) -> Int {
//计算next
var next: [Int] = [0, 0];
//自身匹配，i表示主下标，j表示匹配下标
var i = 2, j = 0;
while i < mode.count {
if(mode[i - 1] == mode[j]){
next[i] = j + 1;
i += 1;
j += 1;
}else{
if(j == 0){
i += 1;
}
//已经匹配的部分有可能会有首尾相同的情况
j = next[j];
}
}
//算法同自身匹配
i = start;
j = 0;
while i < src.count {
if(src[i] == mode[j]){
i += 1;
j += 1;
if(j == mode.count){
return i - mode.count;
}
}else{
if(j == 0){
i += 1;
}
j = next[j];
}
}
return -1;
}
3.2使用js实现
function simpleSearch(src, mode, start){
for(let i = start; i < src.length; i++){
let miss = false;
for(let j = 0; j < mode.length; j++){
if(i + j >= src.length){
miss = true;
break;
}else if(src.charAt(i + j) != mode.charAt(j)){
miss = true;
break;
}
}
if(!miss){
return i;
}
}
return -1;
}
function kmpSearch(src, mode, start){
let next = [0, 0];
let i = 2;
let j = 0;
while (i < mode.length) {
if(mode.charAt(i - 1) == mode.charAt(j)){
j++;
i++;
next[i-1] = j;
}else{
if(j == 0){
i++;
}
j = next[j];
}
}
i = start;
j = 0;
let found = false;
while (i <= src.length) {
if(src.charAt(i) == mode.charAt(j)){
i++;
j++;
if(j == mode.length){
found = true;
break;
}
}else{
if(j == 0){
i++;
}
j = next[j];
}
}
if(found){
return i - mode.length;
}else{
return -1;
}
}
4.0 复杂度分析
- 我们选取复杂度最大的一种模型来分析，即：模式串所有字符都相同，源串和模式串总是在最后一位失配。
- 令源串为 “aaaabaaaabaaaab”，匹配串为 “aaaaa”。
- 匹配串的next数组为：[0,0,1,2,3]
- 首次匹配会在第5位失配，比较次数为5。
- 模式串回到3，进行一次比较即会失配，比较次数为1。
- 模式串回到1，进行一次比较即会失配，比较次数为1。
- 模式串回到0，同时源串下标加1。此时源串下标为6，匹配串下标为0。根据源串特点，此时会不断重复4-7的过程。
- 根据上述分析，我们推到一般情况，长度为n的源串，长度为m的匹配串，会形成一个周期性匹配，周期次数为n/m。
- 很容易看到一个周期内的复杂度小于O(2m)，所以整体复杂度小于 O(2m*n/m)=O(2n)，即复杂度为O(n)。
- 计算next数组的算法和匹配算法相同，因此复杂度为O(m)。
- 所以KMP算法整体复杂度为O(m+n)。
