字符串匹配 KMP算法

46 阅读 0 评论 31 点赞

我是靠谱客的博主重要红牛，最近开发中收集的这篇文章主要介绍字符串匹配 KMP算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述：字符串匹配即查找待匹配字符串（模式串）p在主串s中的位置。一般处理这种问题往往采用简单粗暴的方法——暴力匹配法。所谓暴力匹配法，就是对主串s的每一个字符与要匹配的字符串p的每个字符进行逐一匹配。但暴力匹配效率比较低，经典算法KMP效率更高。

例：主串s=“abcdeabcdxabc”，模式串p=“abcdx”。结果应该返回5。

暴力匹配的图解如下：
在这里插入图片描述
代码如下：


public class 字符串匹配暴力破解 {
public static void main(String[] args){
String s = "abcdeabcdxabc";
String p = "abcdx";
System.out.println(indexOf(s, p));
}
private static int
indexOf(String s, String p) {
int i=0;
//主串匹配的起点下标
int j=0;
int sc=i;
//主串的移动下标 
//当s剩余的长度小于p时就，p就不可能是s的子串了
while(i<s.length()-p.length()){
if(s.charAt(sc)==p.charAt(j)){
sc++;
j++;
if(j==p.length()) return i;
}else{
i++;
sc = i;
j = 0;
}
}
return -1;
}
}

KMP算法最重要的是得出next数组，next数组的长度和匹配字符串P的长度是相同的。next数组表示当出现失配时应该回溯到那个位置。next数组前两个是确定的，分别是-1和0；-1表示第一个失配时应该i进行自增j从0开始，0表示第二个出现失配j应该回溯到0。KMP算法的特征之一是i不会回溯，正是因为如此才提高了效率。
next数组就是失配位置之前的字符串的前缀和后缀的最大匹配数。
KMP算法的图解如下：
在这里插入图片描述
next数组的求法：
例如：字符串bababb的next数组应该是{-1,0,0,1,2,3}，图解如下，j表示出现失配的位置，k表示j出现失配时应该回溯到的位置。因为前两个-1和0是固定的，所以可以根据前两个递推出后面的回溯值。规律如下：如果p[k]==p[j]或者k小于0，next[j+1] == k+1; 然后j++; k++; 如果不同k继续回溯（k=next[k]）, 直到p[k]==p[j]或者k小于0
在这里插入图片描述

代码如下：


public class 字符串匹配KMP算法 {
public static void main(String[] args){
//String s = "abcdeabcdxabc";
//String p = "xabc";
String s = "babababcbabababb";
String p = "bababb";
System.out.println(KMP(s, p));
}
private static int KMP(String s, String p) {
if(s.length()<0||p.length()<0) return -1;
if(s.length()<p.length()) return -1;
int j = 0;
int i = 0;
//int[] next = {-1,0,0,0,0};
int[] next = next(p);
//kmp算法i是有可能移动到字符串s的后面的。
//所以跳出循环的条件不应该是i <= s.length() - p.length()
while (i < s.length()){
if(j==-1 || s.charAt(i)==p.charAt(j)){
//让i往后移（自增）的有两种情况，匹配成功，i和j同时后移
//第二种是在第一个位置就出现失配

j++;
i++;
}else{
j = next[j];
}
if(j==p.length()) return (i-j);
}
return -1;
}
private static int[] next(String ps) {
int len = ps.length();
int[] next = new int[len];
char[] p = ps.toCharArray();
next[0] = -1;
if(len==1) return next; //防止数组越界
next[1] = 0;
int j = 1;
int k = next[j];
while(j < len - 1){//当next数组最后一位完成赋值后结束循环
if(k<0 || p[j] == p[k]){
next[++j] = ++k;
}else{
k = next[k];
}
}
return next;
}
}

下面是KMP算法的变形，返回字符串p在字符串s中出现的次数，改变匹配成功时的代码即可。i退一格，j=next[j-1]; 也就是说j退回（p.length()-1）位置（也就是字符串的最后一位）失配时应该回溯的位置。
代码如下：


public class 字符串匹配KMP算法 {
public static void main(String[] args){
//String s = "abcdeabcdxabc";
//String p = "xabc";
String s = "babababcbabababb";
String p = "ba";
System.out.println(KMP(s, p));
}
private static int KMP(String s, String p) {
if(s.length()<0||p.length()<0) return -1;
if(s.length()<p.length()) return -1;
int count =0;
int j = 0;
int i = 0;
//int[] next = {-1,0,0,0,0};
int[] next = next(p);
//kmp算法i是有可能移动到字符串s的后面的。
//所以跳出循环的条件不应该是i <= s.length() - p.length()
while (i < s.length()){
if(j==-1 || s.charAt(i)==p.charAt(j)){
//让i往后移（自增）的有两种情况，匹配成功，i和j同时后移
//第二种是在第一个位置就出现失配

j++;
i++;
}else{
j = next[j];
}
if(j==p.length()){
count++;
i--;
j = next[j-1];
//return (i-j);
}
}
return count;
//return -1;
}
private static int[] next(String ps) {
int len = ps.length();
int[] next = new int[len];
char[] p = ps.toCharArray();
next[0] = -1;
if(len==1) return next; //防止数组越界
next[1] = 0;
int j = 1;
int k = next[j];
while(j < len - 1){//当next数组最后一位完成赋值后结束循环
if(k<0 || p[j] == p[k]){
next[++j] = ++k;
}else{
k = next[k];
}
}
return next;
}
}