欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

KMP匹配算法

程序员文章站 2024-02-26 22:23:46
...

KMP中next数组的求法,及kmp的完整代码,以及kmp的算法理解。

朴素匹配算法改进得到KMP算法。

KMP匹配算法

如果我们知道T中'a'与T中后面的字符均不相等,而且T串的第二位'b'与S串中第二位'b'已经判断相等,那T中的首位'a'和S串第二位时可以不用再去判断了,他们是绝对不可能相等的。

T[0] !=T[1] && T[1] == S[1] ---> T[0]!=S[1]

举个栗子,完整分析

主串S = "abcababca"  子串T="abcabx"(从下标1开始)

第一步:前5个字符完全相等,第6个不相等,根据文章开头说的,T的首字母和后面第2、3位字符俊不等,那么S[2],S[3],和T[1]肯定不会相等,那么朴素算法的②③步都是多余的。

KMP匹配算法

第二步:T[1]与T[4]的'a'字符,T[2]与T[5]的'b'字符是相同的,在①的时候,T[4],T[5]就已经和S[4],S[5]比较过,是相等的,那我们可以断定T[1],T[2]和S[4],S[5]肯定也是相等的,那么④⑤这两步也是可以省略的。

那就只剩下:

KMP匹配算法

原本(朴素匹配)我们在①时,i=6,i值经过2,3,4,5变化,到⑥i值又回到6。但是上面一张图,i值是不回溯的,只有j值在变。

而j值也只在 子串T的首字符与自身后面字符相同的时候才会发生变化,与主串变化无关。

求next的数组值需要了解一下前后缀,求next值就是利用前后缀的相似度。

KMP匹配算法

栗子分析

KMP匹配算法


完整代码

代码与上图的函数式有点区别:

next[0] = -1;

其他情况等于 0;

相等的时候,next值为前后缀的相同字符数。

public class KMP {
	private String str;    //主串
	private String subStr;    //子串
	private int[] next;    //子串的next数组
	
	public KMP(String str,String subStr){
		this.str = str;
		this.subStr = subStr;
		next = getNextValue();
	}
	
	//获得子串的next数组
	public int[] getNextValue(){
		int len = subStr.length();
		int[] result = new int[len];
		int i=0,j=-1;	//i代表后缀,j代表前缀。
		result[0] = -1;
		
		while(i<len-1) {
			//如果前缀与后缀相等,next[j+1] = next[j] + 1
			if(j==-1 || subStr.charAt(i) == subStr.charAt(j)) {
				++i;
				++j;
				result[i] = j;
			} else {
				//前缀与后缀不相等,j回溯,
				j = result[j];
			}
		}
		return result;
	}
	
	//匹配
	public int kmp() {
		int startIndex = -1;   //匹配到子串的下标
		int slen = str.length();    //主串长度
		int subLen = subStr.length();    //子串长度
		int i=0,j=0;
		while(i<slen-1){
			//当j=-1时,代表着匹配的第一个字符
			if(j==-1 || str.charAt(i)==subStr.charAt(j)){
				++i;
				++j;
			}else{
				//不相等,直接回溯到合适的位置,主串i值保持不变,而不是朴素匹配的一步步回溯。
				j = next[j];
			}
			//子串从下标0开始与子串匹配,j等于子串长度,代表找到了匹配串
			if(j == subLen-1){
				startIndex = i-subLen+1;
				break;
			}
		}
		return startIndex;
	}
	
	public static void main(String[] args) {
		KMP kmp = new KMP("goodgoole","goole");
		for(int i=0;i<kmp.next.length;i++){
			System.out.print(kmp.next[i]);
		}
		int index = kmp.kmp();
		System.out.println("startIndex:" + index);
	}
}