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
在上面的方法中,主串每次都要回溯到最开始,从头开始比较。
而子串当前匹配失败字符之前的字符是匹配成功的,可以利用这个特性,把子串回溯到正确的位置即可,主串不用变。 比如下面这种情况,只需要子串回溯到第三个位置即可。
通过计算子串前后缀相同元素长度来确定回溯位置。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;
}