不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

KMP

有两个字符串,即pattern和value串,从value串里面匹配是否存在pattern串。

双指针

从主串的第一个字符起与子串的第一个字符进行比较,若相等,则继续逐对字符进行后续的比较;若不相等,则从主串第二个字符起与子串的第一个字符重新比较,以此类推,直到子串中每个字符依次和主串中的一个连续的字符序列相等为止,此时称为匹配成功。

public boolean doublePoint(String str, String pattern){
		int n=str.length(),m=pattern.length();
		int i=0,j=0;
		while (i<n && j<m){
			if(str.charAt(i)==pattern.charAt(j)){
				i++;j++;
			}else{
				i=i-j+1;// 不相等,主串回溯
				j=0;
			}
		}
		if(j>=m) {
			return true;
		}else{
			return false;
		}
	}

KMP

在上面的方法中,主串每次都要回溯到最开始,从头开始比较。
而子串当前匹配失败字符之前的字符是匹配成功的,可以利用这个特性,把子串回溯到正确的位置即可,主串不用变。 比如下面这种情况,只需要子串回溯到第三个位置即可。
kmp

通过计算子串前后缀相同元素长度来确定回溯位置。next数组的计算规则:next数组是将前后缀串相同元素长度整体向右移一位,并人为规定next数组的第一个元素值是-1,因为一个字符串的第一个字符的前面不可能有其他字符,所以就不会存在所谓的前后缀相同元素.

next 的值表示当前位置 需要回溯的位置

    public int[] next(String needle){
		int n=needle.length();
		int[] next=new int[n];
		next[0]=-1;
		int i=1,j=-1;
		while(i<n){
			if(j==-1 || needle.charAt(i-1)==needle.charAt(j)){
				j++;
				next[i++]=j;
			}else {
				j=next[j];
			}
		}
		return next;
	}
	public boolean kmp(String haystack, String needle){
		int n=haystack.length(),m=needle.length();
		if(m<=0) return true;
		if(n<=0) return false;
		int[] next=next(needle);
		int i=0,j=0;
		while(i<n && j<m){
			if(j==-1 || haystack.charAt(i) == needle.charAt(j)){
				i++;j++;
			}else{
				j=next[j];
			}
		}
		if(j>=m) return true;
		return false;

	}

算法之字符串模式匹配


目录