KMP算法的一些理解

一名大三狗，这段时间复习了下数据结构，准备写点东西加深印象。这里就简单谈一下我对KMP算法的理解。

KMP算法是一种关于字符串的模式匹配算法，是对朴素匹配算法的一种改进。KMP算法之所以优于朴素匹配算法，是因为它利用next数组实现回溯的次数的减少。所以这篇文章我就围绕next数组写一写我的所得。

KMP算法要干的事`

next数组作用

next数组的获得

next数组算法实现解析

KMP算法的实现

KMP算法要干的事

两个字符串S与T

String	1	2	3	4	5	6
S	a	b	a	b	a	f
T	a	b	a	f

(注：加粗部分为正在对比的字符）

当匹配到S第4个字符和T第4个字符不一样时

朴素匹配模式的做法是 : 将T第1个字符与S的第2个字符进行匹配
| String|1 | 2|3 |4|5|6|
|–|--|–|--|–|--|–|--|–|--|–|--|–|
| S|a | b| a |b|a|f
| T ||a|b|a|d|

使用了next数组的KMP算法的做法是：将T第2个字符与S第4个字符比较

String	1	2	3	4	5	6
S	a	b	a	b	a	f
T			a	b	a	d

可以认为KMP利用next数组直接将字符串T“滑动”两个字符，从而减少了一个对比项
这就KMP算法对比朴素算法所改进的地方

2.next数组作用

上文中 , 字符串T "abad"的 next数组为：

j	1	2	3	4
模式串 T	a	b	a	d
next[j]	0	1	1	2

（j为模式串T的指针）

这个表的意义就是：
当模式串T的第 j个字符与字符串S第 i 个字符不匹配时，将模式串T上的指针回溯到 next [ j ] 上，再进行比较。
也就是说将模式串T向右"滑动"了 next [ j ] 个字符。

next数组的获得

通过上文，不难看出KMP算法的核心之处就是next数组了
现在可以讨论一下 next数组究竟是怎么来的了

这里介绍下前缀和后缀的概念

前缀：指的是字符串的子串中从原串最前面开始的子串，如abcd的前缀有：a,ab,abc
后缀：指的是字符串的子串中在原串结尾处结尾的子串，如abcd的后缀有：d,cd,bcd

这里用上文的模式串T进行说明,以求解 next [ 4 ]=2 为例

j	1	2	3	4
模式串 T	a	b	a	d
next[j]	0	1	1	2

先用前面的字符得到一个相等的前缀与后缀

即当模式串T的第4个字符：d 与字符串S 的第 i 个字符不匹配时：

j	1	2	3	4
模式串 T	a	b	a	d
前缀	a			j
后缀			a	j

next [ j ] 的值就为前缀的最后一个字符的指针+1
即 next [ 4 ] 就为 2

抽象化的解释就是:
KMP算法的一些理解

next数组算法实现解析

话不多说，先贴上java实现的 getNext（）方法

 public static int[] getNext(String T) {
		int[] next = new int[T.length()];
		next[0] = -1;
		int j = 0;
		int k = -1;
		while (j < T.length()-1 ) {
			if (k == -1 || T.charAt(j)==T.charAt(k)) {
				next[++j] = ++k;
			} else {
				k = next[k];
			}
		}
		return next;
	}

这段代码的难点主要是while循环的if(){}else{}语句块了
所以这里我就主要谈谈我对这里while循环作用的理解

这里我先解释 if(){} 这个代码块的内容

if (k == -1 || T.charAt(j)==T.charAt(k)) {
				++j;
				++k;
				next[j] = k;
			}

先上个图片

KMP算法的一些理解
这个图片我先解释一下，解释完if语句块的意思就清楚了
当模式串T中的第 j+1 个字符匹配失败时，图片显示了一条暗含的信息:即 next[ * j+1* ]前面的所有的next[]值是已知的，
那么next [ j ]是已知的，换句话说就是 j 前面存在一对已知且相等的前缀Ta与后缀Tb。
这时，如果满足T中第 k+1个子和第 j 个字符相等的话，那么第 j+1个字符前就存在了一对相等的前缀和后缀，
使得next [ j+1 ]= k+1。

当然这是if语句满足的情况，接下来讨论另一种情况 :
即 T中第 k+1个子和第 j 个字符不相等 的情况，如果不相等的话，就是执行else{}语句的内容了。
所以下来，就可以分析了一下else{}语句的内容

 else {
				k = next[k];
			}

next[]值的本质就是去找前缀与后缀，但此时的前缀Ta与后缀Tb又无法满足要求，所以我们需要重新寻找一个 “k” 值，来构造一个新的前缀 Ta’ 和后缀 Tb’

先上图
KMP算法的一些理解
在重新定位 k 前不妨用 s 来取代 k 原来的位置，
则 s < j, 那么next [s] 就是已知的了，那么s前面就存在Ta’与Ta’’，且Ta’=Ta’’；
由已知且相等的前缀Ta与后缀Tb，不难得出：
前缀Ta 中存在 前缀Ta’ 和 前缀Ta’’ ,且 Ta’ = Ta’’ ；
后缀Tb 中取与 Ta’’ 长度相等的 后缀Tb’，因为 Ta=Tb ，所以 Ta的后缀和Tb的后缀也相等，即 Tb’ = Ta’’；
以上可知，Ta’=Tb’。
那么，k 的位置就可以定为 Ta’ 的最后一个字符
问题就变成了若个模式串T中第 k+1 个字符与第 j 个字符是否相等的问题，
如果相等，则next [ j+1] =k+1；不相等的话，就需要重新定位 k 了，同上。

KMP算法的实现

接下来直接贴KMP的算法实现，这里就不多赘述了

public class KMP {
 	public static void main(String[] args) {
		String s=new String("sadksdjfksdfj");
		String t=new String("ksdf");
		int position=KMP(s,t);
		System.out.println(position);
	}

	public static int[] getNext(String T) {
		int[] next = new int[T.length()];
		next[0] = -1;
		int j = 0;
		int k = -1;
		while (j < T.length()-1 ) {
			if (k == -1 || T.charAt(j)==T.charAt(k)) {
				next[++j] = ++k;
			} else {
				k = next[k];
			}
		}
		return next;
	}
	public static int KMP(String t,String p) {
		char[] cht=t.toCharArray();
		char[] chp=p.toCharArray();
		int i=0;
		int j=0;
		int [] next=getNext(p);
	
		while( i<cht.length && j<chp.length ) {
			if( j==-1 ||cht[i]==chp[j] ) {
				i++; j++;
			}else {
				j=next[j];
			}
		}
	
		if(j==chp.length) {
			return i-j;
		}else {
			return -1;
		}
	
	}

}

第一次写博客，由于没在网上找到相似的图片，所以本文图片都是自己在win10自带的画图工具自己做的（哈哈，想死的心都有了，手动滑稽），所以难免粗糙，不足之处请多多包涵。

KMP算法的一些理解

相关推荐