串的应用与kmp算法讲解--学习笔记

时间:2020-12-12 17:56:09

串的应用与kmp算法讲解

1. 写作目的

平时学习总结的学习笔记,方便自己理解加深印象。同时希望可以帮到正在学习这方面知识的同学,可以相互学习。新手上路请多关照,如果问题还请不吝赐教。

----------

2. 串的逻辑存储

       串指的是字符串,是一种特殊的线性表,特殊性在于只能存储字符,即可以使用顺序存储也可以使用链式存储,简单的谈一下两种存储结构的优缺点。

顺序存储

       顺序存储使用的是数组,既然是数组就是申请固定空间,当串需要拼接,替换时,可能会对数组进行扩容,这种操作就比较耗时,而且有时数组空间利用率很低,也浪费了一部分空间。但是优点也是显而易见的,定位速度快。

链式存储

       链式存储不拘束于空间大小,需要多少空间就链上多少个节点。但是如果每个节点都只存一个字符,那么无疑是浪费了空间,如果存多个字符,那么在字符查找上需要花费更多的时间,而且链表本身查找速度慢。

我的观点

       更倾向于顺序存储,毕竟字符串更为频繁的操作是查找功能,相较于链式存储,牺牲一点空间,换取更快查询的速度。


3. 串的应用--暴力查找

       下面说说串的应用:子串的查找。这个应该很熟悉,有好多应用场景是希望在一个主串中找到子串。可能想找到子串的位置,也可能想判断是否存在,或者替换,全部替换等,这就需要我们能完成最基本的操作,找出子串。

       下面这个例子可能是我们最容易想到的算法,直接找:两个循环嵌套,外层循环(i)逐一遍历主串每个字符,判断是否能和子串首字母匹配,如果匹配就继续判断第二个字符,直到把子串遍历完,就是找到了。但是如果中途某个字符不匹配,就把 i 回溯,回到匹配最初的地方,来进行下一个字符的首字母匹配。基本过程如下:

`public static int matchPattern(String origin,String aim) {

	char[] origins = origin.toCharArray();
char[] aims = aim.toCharArray(); for(int i = 0; i < origins.length; i++) { int j = 0,k = i;
for( ; j < aims.length;k++,j++ ) { if(origins[k] != aims[j]) {
break;
}
}
if(j == aims.length) {
return i - j;
}
}
return -1;
}`

       这个方法应该都可以想到,但是这样写会有问题。问题就是:

1.

2.

串的应用与kmp算法讲解--学习笔记

串的应用与kmp算法讲解--学习笔记

3.

串的应用与kmp算法讲解--学习笔记

4.

串的应用与kmp算法讲解--学习笔记

5.

串的应用与kmp算法讲解--学习笔记

       似乎感觉很正常,但如果仔细查看会发现,每当快要匹配成功的时候,因为一个字符的不匹配,就要回头再来,如果字符串很长,而目标字符相似度很高,就会一直重复这样的比较,重要的是其实我们可以根据已知的比较结果来减少比较的次数,来优化这种算法。


4. KMP算法

       简单说一下这个算法的背景,KMP的由来。

       KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。

       用我自己的话概述就是在匹配字符串过程中,因为某个字符匹配失败后,根据已有匹配成功的串推算出下次子串需要移动的位置,从而达到减少不必要匹配次数,实现快速匹配。那么重点就来了,如何推算出子串需要移动的位置? 我怎么知道这样移动后能一定能保证不会有遗漏。那下面我们就一起来分析一下(还是使用上面的例子,为了描述方便,我们把主串称为o(origin),子串称为a(aim) )。

  1. 第一步这样匹配没问题。

    串的应用与kmp算法讲解--学习笔记

  2. 第二步这样匹配就出现问题了。 问题是上一步 i 已经移动到 4(数组下标),就因为o[4] != a[4],本次匹配失败,i 需要回溯到 1,j 需要回溯到 0 ,之前的匹配结果信息根本没有派上用场。

    串的应用与kmp算法讲解--学习笔记

    因为根据已经匹配信息,o[0] = a[0],o[1] = a[1],o[2] = a[2],o[3] = a[3],前4位是对应相等的,而且o[2] = a[0],o[3] = a[1],我们完全可以这样移动:

    串的应用与kmp算法讲解--学习笔记

    这样的话可以不用比较o[1]与a[0],o[2]与a[0],o[3]与a[1],直接比较o[4]与a[2],省去了不必要的步骤。那么我们继续往下分析,显然o[4] != a[2],因为o[2] = a[0],o[3] = a[1],而且a[0],a[1]不相等,我们可以推断出,o[3] != a[0],所以这一比较步骤也可以省略,直接比较a[4]与a[0]。最终得到结果

    串的应用与kmp算法讲解--学习笔记

    这样的比较方式,是我们可以接受的,根据已知匹配信息省略了许多比较操作,提高效率。

  3. 那可能有人就要问了,你是怎么知道确切的移动位置,可以让 j 定位到合适的位置,这也就引出了KMP算法的核心的部分,求next[]。next[]有什么作用,next[0],next[1]....next[n]的含义是什么?next是存放对应子串字符冲突后,需要移动 j 的位置。举个例子:next[4] = 2,意思是在 j = 4的位置上子串和主串不匹配,那么主串 i 不需要回溯,直接把 j 回溯到 2,进行比较,也就是把next[]的每个值都求出来,我们就可以轻松准确的更改 j 的位置。了解了next[]的用途,下面我们来学习next[]是如何求出来的。

  4. 拿之前的例子作为说明:

    串的应用与kmp算法讲解--学习笔记

    o[4]与a[4]冲突,前4位对应相等(首要条件),我们要是想根据前4位相等来推算位置,应该会出现2中情况。一:子串前4位互不相等(a[0],a[1],a[2],a[3]没有一个相同的),根据以上2个条件(o,a对应相等),直接可以推算,a[0]下次应该直接和o[4]比,原因就是a[0]不会和o前4位任意字符相等。 二:子串前4位有字符相等,而且是前后缀对应相等,也是可以推算位置。 插播一下前后缀知识。

    例如一串字符 "abadaba"

           前缀:{"a","ab","aba","abad","abada","abadab"}

           后缀:{"a","ba","aba","daba","adaba","badaba"}

    那么前后缀最长匹配相等串"adaba"。

    回到刚才的问题,对于串"abab",最长匹配相等串为"ab"。那么我们是可以这样理解的:

    串的应用与kmp算法讲解--学习笔记

    我们分析的是a的前后缀关系,但前提提交是o,a对应位置相等,所以a的前缀就对应了o的后缀,这样我们可以直接移动 j 2的位置。理论基本就这些,我们通过代码来实现一下:

     public static int[] getNext(String aim,int length) {
    char[] chars = aim.toCharArray(); int i = 0,j = -1; //next数组长度和aim长度是相等的,因为每一个字符比较出冲突都需要有对应j的位置
    int[] next = new int[length]; //第0个位置前是没有前后缀的,所以next[0]我们规定为 -1.
    next[0] = -1;
    //第1个位置不匹配,前面只有一个字符,我们只能把j移动到0.
    next[1] = 0; //注意:这里 i < length -1,而非是 i < length。原因就是 i在循环内部先++,再赋值,如果是 < length会数组越界。
    while(i < length-1) { //判断如果对应字符相等,就累加前后缀相同字符长度
    if( j == -1 || chars[i] == chars[j] ) {
    next[++i] = ++j;
    }else {
    //注意:就这一句话,困扰我了2天,也许2是比较菜,不过我在文章中,重点解释一下,见文章。
    j = next[j];
    }
    }
    return next;
    }

重点来了

我们在求解next的时候并不需要o,只需要a就可以得出。我们只需要找出a中前后缀匹配长度,即可。那么我们的方法就是让a和a自己比较。比较的过程如下:

  • a[0]与a[1]比较,不相等

    串的应用与kmp算法讲解--学习笔记
  • a[0]与a[2]比较,相等,next[ ++i ] = ++j, next[3] = 1。 意思是什么呢? 可以这样理解,在第3个字符前面的字符中,前后缀最大公共长度为1,也就是有1个公共字符,"a"。那么我知道这个信息有什么用处呢?用处就是当j在3位置上匹配失败,直接改变j为1来继续比较。

    串的应用与kmp算法讲解--学习笔记
  • a[1]与a[3]比较,相等

    串的应用与kmp算法讲解--学习笔记
  • a[2]与a[4]比较,不相等

    串的应用与kmp算法讲解--学习笔记

    因为只是a[2]与a[4]不等,我们还不能确定具体的公共长度(next[4]的值),接下来我们需要回溯比较,a[4]与a[1],然后a[4]与a[0],如果这样比较多话,就又成了普通的暴力比较 ,我们可以根据已有的结果来推算。下面我来说一下困惑我2天的问题,j = next[ j ]

    现有我们已经推算的结果:next[ 0 ] = -1, next[ 1 ] = 0, next[ 2 ] = 0, next[ 3 ] = 1,next[ 4 ] = 2。按照算法来说,就是, j = next[2],j = 0。

           我之前一直认为 next[j] 的值代表的就是 j 需要移动的下标,所以很是不能理解把next[4]的值有放到next[]中(怎么能把下标放入到next[]中),也就是next[next[4]],next[4]很清晰的说明是当 j = 4 的位置有字符冲突时,把 j 移动到next[4],也就是2,那next[2]又是啥意思? 也就是实在搞不懂next[next[4]]。2天总是想着这个事,也继续在网上查阅资料,看有没有人和我同样有这个疑问。最后在不断的浏览中,感觉有可以说通的答案了,next[j] 也表示 0 ~ j-1 字符中前后缀最大长度,那么当next[4]失配后,next[4] = 2, 我们知道前面的4个字符,最大公共前后缀长度为2,那么next[2]就是在前2个字符当中再寻找最大前后缀公共的长度,因为是自身和自身比较,公共前后缀字符"ab"和 i=2 时前面的字符是一样的,所以在公共前后缀中再找相同前后缀即为在 i = 2之前找,也就是next[2]的值,相信到这里已经对这个疑问得到解答了。

    串的应用与kmp算法讲解--学习笔记

next[ ]的求解我认为是kmp的核心,这个了解完之后,所剩内容不多。引用代码来使用next[ ]完成主串与模式串的查找吧。稍微改动了暴力求解的代码。

public static int kmp(String origin,String aim) {

	char[] origins = origin.toCharArray();
char[] aims = aim.toCharArray(); int[] next = getNext(aim,aim.length()); for(int i = 0; i < origins.length; i++) {
int j=0;
for( ; j < aims.length; ) { if(origins[i] != aims[j]) {
//改动
if(j == 0) {
break;
}
j = next[j];
}else {
i++;
j++;
}
}
if(j == aims.length) {
return i-j;
}
}
return -1;
}

5. 聊一下kmp的改进方案:

举例说明,有一种情况,我们的next[ ]有待优化,是这样一种情况。模式串:"aaaaaaab",显然我们的结果是next[]{0,0,1,2,3,4,5,6}。当和我们的主串"aaaaaaacaa....",会导致以下情况:

1.

串的应用与kmp算法讲解--学习笔记

2.

串的应用与kmp算法讲解--学习笔记

3.

串的应用与kmp算法讲解--学习笔记

4.

串的应用与kmp算法讲解--学习笔记

那我们如何改进呢?就是发现模式串中出现连续相等字符就让nextVal[ i ] = nextInt[ j ],解释一下就是: 回溯到上一个字符需要回溯的位置,因为2组前后缀对应想等,那就和上一个做相同处理。

public static int[] getNextVal(String aim,int length) {
char[] chars = aim.toCharArray(); int i = 0,j = -1; //next数组长度和aim长度是相等的,因为每一个字符比较出冲突都需要有对应j的位置
int[] nextVal = new int[length]; //第0个位置前是没有前后缀的,所以next[0]我们规定为 -1.
nextVal[0] = 0;
//第1个位置不匹配,前面只有一个字符,我们只能把j移动到0.
nextVal[1] = 0; //注意:这里 i < length -1,而非是 i < length。原因就是 i在循环内部先++,再赋值,如果是 < length会数组越界。
while(i < length-1) { //判断如果对应字符相等,就累加前后缀相同字符长度
if( j == -1 || chars[i] == chars[j] ) { i++;
j++;
//相较于getNext()改动的地方
if(chars[i] == chars[j]) { // i == j, i+1 == j+1
nextVal[i] = nextVal[j];
}else {
nextVal[i] = j;
} }else {
//注意:就这一句话,困扰我了2天,也许是比较菜,不过我在文章中,重点解释一下,见文章。
j = nextVal[j];
}
}
return nextVal;
}

参考文档:

《大话数据结构》

如何更好的理解和掌握 KMP 算法?

怎么理解kmp算法中的next数组?

从头到尾彻底理解KMP(2014年8月22日版)