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

KMP算法之字符串匹配

程序员文章站 2022-07-14 07:57:59
...

KMP算法之字符串匹配

  1. 暴力匹配

通过起始匹配的字符开始继续匹配,若匹配成功,则长度等于str2的长度,否则回到匹配的第二个位置重新开始

package Kmp;
public class Baolipi {
    //暴力匹配算法进行字符串匹配
	public static void main(String[] args) {
		String str1 ="明天你好吗 明天你好挖 明天你好明天你好哈哇哇哈";
		String str2="明天你好哈"; //匹配的起始下标是16
		System.out.println(Ser(str1,str2));
	}
   //暴力匹配方法,返回匹配的第一个下标
	public  static int Ser(String str1,String str2) {
		char[] s1 = str1.toCharArray();
		char[] s2 = str2.toCharArray();
		int s1len = s1.length;
		int s2len = s2.length;
		int i = 0,j = 0;
		while(i< s1len && j<s2len) {
			//匹配第一个字符,然后继续匹配
			if(s1[i]==s2[j]) {
				i++;
				j++;
			}else {
				i = i-(j-1); //回到起始的第二个位置接着匹配
				j = 0; //重新来过
			}
		}
		//匹配成功条件
		if(j==s2len) {
			return i-j; //开始匹配的起始下标
		}else {
			return -1;
		}
	}
}
  • KMP匹配算法

KMP算法之字符串匹配

其核心思想是:在进行匹配过程中,若母串的字符有一段与子串的一段匹配,这样也就是没有匹配到最大子串,

其下标不应该回到之前母串走过的下标,而是从部分匹配过的词下一个开始重新匹配,如下面的:

(1)由于部分匹配词为AB,所以下次开始从字符串长度-部分匹配词开始匹配,主要是记录部分匹配值的位置

KMP算法之字符串匹配KMP算法之字符串匹配

KMP算法之字符串匹配

(2)这样就又有AB部分匹配,所以下次得后移两位开始重新匹配

KMP算法之字符串匹配

(3)

KMP算法之字符串匹配

代码:

package Kmp;

import java.util.Arrays;

public class kmp {

	public static void main(String[] args) {
		String s1 ="BBC ABCDAB ABCDABCDABDE";
		String s2 ="ABCDABD";
		//部分匹配词表
		int[] next =KmpNext(s2);
		System.out.println(Arrays.toString(next));
		int index = pipei(s1, s2,next);
		System.out.println(index);
	}
	//编写匹配的方法
	public static int pipei(String s1,String s2,int[]next) {
		for(int i = 0,j=0;i<s1.length();i++) {
			while(j>0 && s1.charAt(i)!=s2.charAt(j)) {
				j =next[j-1];
			}
			if(s1.charAt(i)==s2.charAt(j)) {
				j++;
			}
			if(j == s2.length()) {
		      return i-j+1;
			}
		}
		return -1;
	}
	//编写子串的部分匹配词表
	public static int[] KmpNext(String s2) {
		//创建一个next数组保存部分匹配词
		int[] next = new int[s2.length()];
		next[0] = 0; //若子串为一个字母,则无前缀和后缀匹配
		//开始进行匹配词的编写,i表示后缀匹配的开始如ABCDAB,这里指向下标4(AB)开始
		//j表示前缀匹配的开始,从0开始
		for(int i =1,j = 0;i<s2.length();i++) {
			//如果匹配了前缀与后缀的部分就错误:s2.charAt(i)!=s2.charAt(j)
			while(j>0 && s2.charAt(i)!=s2.charAt(j)) {
				j = next[j-1]; //退回到前缀的开始位置,KMP核心思想
			}
			//先遍历到后缀匹配的开始下标
			if(s2.charAt(i)==s2.charAt(j)) {
				j++; //继续匹配前缀与后缀
			}
			next[i] = j;
		}
		return next;
	}

}