KMP算法

串

字符串是一种特殊的线性表, 其逻辑结构与线性表相同, 只是在数据类型上进行了约束, 要求元素全是字符类型. 串可以顺序存储, 链式存储, 或者堆存储. 堆结合了顺序和链式的优点, 实际在构造串也是采用的堆结构来存储, 能够方便动态扩展.

方便理解可以使用顺序存储.

// 串的定义
//typedef struct{
//    char str[maxSize+1];
//    int length; 
//}Str;

// 或者
typedef struct{
    char *ch;
    int length;
}Str;

字符串以'\0'作为结束标记. 串的基本操作有赋值, 取串长, 串比较, 求子串, 串清空, 串连接等. 在实现起来没有多大难度, 就稍微注意一下结束标记的处理即可.

字符串匹配

对一个串中的某子串定位操作称为串的模式匹配, 而其中与主串进行对比的子串称为模式串. 在字符串中常用到字符串匹配.

简单模式匹配算法

简单而朴素的匹配算法, 就是将主串与模式串的字符挨个进行比对, 如果相同则逐一比对主串和模式串的下一个元素, 如果不同, 则从主串的下一个元素重复逐个比对的过程. 全部相同则匹配成功, 否则匹配失败.

代码实现如下:

// 简单模式匹配算法
// 假设字符串储存在1 ~ length上 
int index(Str str, Str substr){
    int i = 1, j = 1, k = i;
    // 其中i和j分别用来表示主串和子串的位置, k用来暂存主串被比对的位置 
    while(i <= str.length && j <= substr.length){
        if(str.ch[i] == substr.ch[j]){
            ++i;
            ++j;
        } 
        else{
            j = 1;
            i = ++k; // 匹配失败 i从主串下一个位置开始 
        }
    }
    // 到这里有两种可能性 一个是原串被遍历完了 还有就是子串被遍历完了 
    // 如果是子串遍历完了说明匹配成功 
    if (j > substr.length)
        return k;
    else
        return 0; // 因为假设字符串从下标1开始, 0是没有字符的
}

这个简单的算法就是单纯的暴力匹配, 没有任何的预处理, 如果字符串长为n, 模式串长为m, 那么最坏时间复杂度为O((n-m+1)*m). 即每次主串与模式串匹配时总能一直搜索到模式串的最后一个字符, 并最后匹配没有成功.

KMP算法

KMP算法是一种经典的字符串匹配算法, 相较于前面所说的简单字符串匹配算法, 在比较速度上有了相当大的提升.

来观察一个问题, 在下述串匹配过程中, 当在箭头所指的位置发生了字符不匹配:

如果是简单字符串匹配算法, 那么很简单, 说明以主串第一个元素A 为起始的字符串无法与模式串相匹配, 将回溯到主串第二个元素B 与模式串第一个元素A 进行比较, 然后继续逐一比较下去…

继续观察如何才能使得模式串指针直接移动到再次能够与箭头所指的主串字符B 与模式串相比较的位置:

由于主串第二个字符是B, 模式串第一个字符是A, 发生不匹配, 主串指针下移, 主串的第三四五个字符和模式串的第一二三个字符匹配, 又回到了对模式串某字符主串字符B 的比对.

除去简单字符串匹配, 有没有更取巧的办法, 利用模式串自身的特点, 或者说利用在主串和模式串发生不匹配时已经匹配字符的信息, 来压缩这个比较的过程呢?

继续逐一完成主串和模式串的比对, 又发现有一处不匹配.

如果是简单字符串匹配又要逐一后移, 直到达到下述状态, 才能再次进行主串中所指的B 和模式串比对.

经过这两个例子, 隐隐约约发现点问题. 总会出现一种状态, 模式串中某个字符与主串字符发生不匹配, 但在这之前的所有字符都已经匹配了. 如果使用简单字符串匹配, 效率极其低下. 如果模式串的前半部分(从起始处向后取)和后半部分(从不匹配点向前取)有完全相同的子串, 那么很明显如果前半部分与主串完全匹配, 那么后半部分也一定与主串完全匹配, 那就不用重复进行比对了!

为方便比较, 我将两次比对放在一起, 比如:

这里从起始处向后取, 即黄色框内的ABA 和从不匹配点向前取的白色框内的ABA 就是完全相同的子串, 这对子串称为公共前后缀. 正是因为这对前后缀完全相同, 所以发生字符不匹配时, 才能直接使得模式串的指针停留在前缀的下一个位置上, 不再重复进行前缀的比对, 这也是简单字符串匹配和KMP算法的最大不同, 即模式串的比较指针不回溯.

指针不回溯意味着对大规模的外存中的字符串匹配操作可以分段进行. 先读入内存一部分进行匹配, 完成后再写回外存, 确保在匹配时不需要将之前写回外存的部分再次读入, 减少了IO操作, 从而提高了效率.

在取前后缀时, 可能会有多对, 那应该取哪一对呢? 以上述发生不匹配的图为例, 从左右分别取, 应该可以形成A-A, ABA-ABA, ABABA-ABABA 三对符合要求的公共前后缀. 其中AB-BA 和 ABAB-BABA不是完全相同的子串, 是倒过来的, 不是公共前后缀. 如果要尽可能的减少重复比对次数, 一定是公共前后缀越长越好, 越长说明已经比对过的字符越多. 同时需要注意, ABABA-ABABA 这对是长度完全和子串长度相等, 再次比对时就失去了意义, 虽然是公共前后缀, 但它应该不能被使用. ABA-ABA 就是最长公共前后缀, 取最长的一对公共前后缀作为指针不回溯的依据.

记住, 模式串的比较指针直接就指向了前缀的下一个位置. 再看一个例子, 加深理解:

在上述叙述的过程中, 发生主串和模式串的不匹配时, 模式串左侧与主串的对应位置一定是匹配的, 换句话说二者是一样的. 那么研究模式串就和研究主串是等价的了, 因此与主串无关, 仅保留模式串, 将指针不回溯的位置记录用数组下来, 当发生不匹配时, 指针就恢复到之前记录的位置即可. 这个数组称为next数组.

为方便, 字符串下标从1开始. 对于模式串:

发生不匹配的模式串下标	最长公共前后缀长度	主串当前与模式串比对的下标	最长公共前后缀
1	0	0(特殊)	-
2	0	1	-
3	0	1	-
4	1	2	`A`
5	2	3	`AB`
6	3	4	`ABA`
7	1	2	`A`
8	1	2	`A`
9	2	3	`AB`
10	3	4	`ABA`
11	4	5	`ABAB`
12	5	6	`ABABA`

总结上述规律, 除去模式串第一个元素外, 主串当前元素与模式串元素比对的下标是最长前后缀长度+1. 如果下标为1发生不匹配, 主串的下一个元素与模式串下标元素为1开始比较. 最坏时间复杂度是O(n+m).

简单匹配升级到KMP

先抛开next数组如何构造不谈, 先看看如何写KMP的代码. 如果KMP完成了简单字符串匹配算法的压缩, 那也应该能够由简单算法升级为KMP算法.

实现KMP代码如下:

int KMP(Str str, Str substr, int next[]){
    int i = 1, j = 1; // 下标从1开始
    while(i < str.length && j < substr.length){
        // 主串指针下移的情况
        if(j == 0 || str.ch[i] == substr.ch[j]){
            ++i;
            ++j;
        }
        // 发生不匹配时模式串指针跳到next数组所指向的位置
        else j = next[j];
    }
    // 遍历完模式串没发现不匹配 说明模式串与主串相匹配
    if(j > substr.length) return i - substr.length;
    else return 0;
}

求next数组

再来看看next数组是如何构建的. 让我们回到之前找最长公共前后缀的过程. 那时曾经说过, 公共前后缀是两段完全相同的子串, 那找最长公共前后缀的过程岂不是也是字符串匹配? 我们仍然要延续不重复做事情的思路, 利用已知信息去求next数组.

如果这样去想, 那么图中Pj所对应的next数组的值与Pt必然是有关联的.

当Pj和Pt的大小未知, 而前面模式串均相同时, 假设在Pj出发生不匹配, 模式串指针会跳转到最长公共前后缀+1处, 即next[j] = t. 有了这个初始条件, 可以根据Pj和Pt的大小关系推出next[j+1].

假设P(j+1)处发生不匹配:

如果Pj = Pt, 那么next[j+1] = next[j]+1 = t+1.
如果Pj != Pt, 就得在这两个串(本质是模式串自己) 中找到最长的公共前后缀, 也就回到了字符串匹配的问题中. 将P(j-t+1) ~ Pj 视为主串, P1 ~ Pt视为模式串, 继续做字符串匹配. 必须向前反复重定位指针, 找到一个位置使得Pj = Pt或满足t = 0, 即将t循环赋值为next[t], t = 0 时, 令next[j+1] = 1.
注意, 因为第二种情况与字符串匹配完全一致, 所以建立next数组的代码一定与KMP算法极其相似:

// 求next数组的方法 substr为模式串 
// j和t与上述图中相同
void getNext(Str substr, int next[]){
    int j = 1, t = 0;
    next[1] = 0; 
    while(j < substr.length){ // j<= substr.length 会使next数组下标越界 
        // 模式串自身匹配
        // t可能被下面的else赋值为0, 在条件并入后会将t置为1
        // 并且第一次执行, 有next[2] = 1, 满足之前推导的结果
        if (t == 0 || substr.ch[j] == substr.ch[t]){
            ++j;
            ++t;
            next[j] = t; // next[j] = length+1 length实际上就是没++前的t
        }
        else t = next[t]; // 模式串指针重定位到next[t] 
    }
}

KMP算法改进

在求next数组时, 会一直用到向”前反复重定位指针”这个操作, 还可以有优化的余地.

在这个例子中出现了连续且完全相同的字符, 在j = 5时发生不匹配, next[j] = 4, 将j重定位到next[j] 上. j又为4, next[j] 又为3… 反复重定位, 直到j为0, 才发现该位置的主串和模式串完全不匹配, 主串和模式串指针都应该后移一位. 在这个过程, 从1到4位置上的字符串是相等的, 应该直接给next[5] 赋值为0.

尝试在next数组的基础上, 构建一个重定向数组, 使得其能够根据之前比较的内容跳过多余的比较, 直接将next[j] 赋值为某个已知的next数组值, 这个数组叫nextval数组.

在上面的图中, j位置的元素反复与Pd, Pc, Pb, Pa都进行了比较, 但明显前三者都是冗余比较, 不能给解决不匹配问题带来好处. 此处的nextval[j] 应该为a.

推广到一般情况, 路径上的元素都不是相邻的, 而现在j之前的nextval数组值都是已知的, 如何求j后的元素k的nextval[k] 呢?

如果k位置上的元素和j位置上的元素相等, 那么nextval[k] = nextval[next[k]], 如果不相等则令nextval[k] = next[k].

归纳为一般步骤:

j = 1时, nextval[j] 赋值为 0, 作为特殊标记
j > 1时:
- 若Pj != P(next[j]), 则nextval[j] = next[j].
- 若Pj = P(next[j]), 则nextval[j] = nextval[next[j]].

求nextval数组的代码可以由求next数组的代码修改而来, 最好对比结合起来看, 实现如下:

void getNextval(Str substr, int nextval[]){
    int j = 1, t = 0;
    nextval[1] = 0; // j=1时nextval[j] = 0
    while(j < substr.length){
        if(t == 0 || substr.ch[j] == substr.ch[t]){
            ++j;
            ++t;
            // 求解next数组时, 有next[j] = t; 那么t可以代替next[j] 
            if(substr.ch[j] != substr.ch[t])
                nextval[j] = t; // nextval[j] = next[j]
            else
                nextval[j] = nextval[t]; // nextval[j] = nextval[next[j]]
        }
        else t = nextval[t];
    }
}