首页 > 代码库 > 字符串模式匹配算法

字符串模式匹配算法

定义:设有主串S和子串t,子串的定位就是要在主串S中找到一个与子串t相等的子串。通常把主串S称作目标串,子串t称作模式串,因此定位也称作模式匹配。

常用两种算法:

1brute-force算法

思路:主串标记指针每次移动一个位置,然后和子串比较,如何相等则返回当前主串指针的位置。

模式匹配过程如图:

           图略

上面算法的缺点:主串指针回溯,当与模式串部分匹配后,每次主指针只移动一个位置。

2.kmp算法

思路:分析模式串,从而避免不必要的回溯。构建模式数组。

过程:模式串t="abcabd",用next数组存放这些‘部分匹配‘信息

            第一个字符‘a‘,规定next[0]=-1;

            第二个字符‘b‘,规定next[1]=0;

            第三个字符‘c‘,前一个字符’b‘,不等于模式t的开头,即next[2]=0;

            第四个字符‘a‘,前面字符串"bc"、"c",都不与模式串t的开头字符串匹配,即next[3]=0;

            第五个字符‘b‘,前面字符串"bca"、"bc"、"a",有"a"与模式串t的开头字符串匹配,即next[4]=1;

            第六个字符‘d‘,前面字符串"bcab"、"cab"、"ab"、"b",有"ab"与模式串t的开头两个字符相等,即next[5]=2;

             。。。

             最后在计算时,每次与主串部分匹配后,主串直接从 匹配不相等的指针出继续匹配,模式串跳转到next数字指向的那个位置,避免回溯。

匹配过程如图:

       图略

不完善的过程:如果出现s="aaabaaaab",t="aaaab"时,会出现主串停留在第四个字符三次,模式串的next数组从3->2->1->0的位置变化,

过程如图:

         图略

改进方式:如果出现s="aaabaaaab",t="aaaab"时,模式中的1,2,3个字符和第4个相等,因此不需要在和第四个字符比较,而可以将模式一次向右滑向第4个字符的位置直接进行i=4,j=0时的字符比较。

 过程如图:

最终算法如下:

public class KMP {
    private final static int maxSize = 100;
	private static  int[] nextval = new int[maxSize]; //next数组 
	
	/*@function 构建模式串的next数组
	 */
	private static void getNext(String s){
		int len = s.length();
		char[] ch = s.toCharArray();
		int j = 0, k = -1;
		nextval[0] = -1;
		while(j < len-1){
			if(k==-1 || ch[j] == ch[k]){
				j++;k++;
				if(ch[j] != ch[k]) nextval[j]=k;
				else nextval[j] = nextval[k];
			}else{
				k = nextval[k];
			}
		}
	}
	
	/*@function 计算字符匹配串的位置
	 */
	private static int KMPIndex(String s, String t){
		int i = 0, j = 0;
		int sl = s.length();
		char[] sc = s.toCharArray();
		int tl = t.length();
		char[] tc = t.toCharArray();
		while(i<sl && j<tl){
			if(j==-1 || sc[i]==tc[j]){
				i++; j++;
			}
			else{
				j = nextval[j];
			}
		}
		if(j>=tl) 
			return (i-tl);
		else 
			return -1;
	}
	
	public static void main(String[] args){
		String s = "abcaabbabcabaacbacba";
		String t = "abcabaa";
		getNext(t);
		int i = KMPIndex(s,t);
		System.out.println(i);
	}
	
}
总结:慢慢吃透。

   

字符串模式匹配算法