KMP算法之字符串匹配
程序员文章站
2022-07-14 07:57:59
...
- 暴力匹配
通过起始匹配的字符开始继续匹配,若匹配成功,则长度等于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匹配算法
其核心思想是:在进行匹配过程中,若母串的字符有一段与子串的一段匹配,这样也就是没有匹配到最大子串,
其下标不应该回到之前母串走过的下标,而是从部分匹配过的词下一个开始重新匹配,如下面的:
(1)由于部分匹配词为AB,所以下次开始从字符串长度-部分匹配词开始匹配,主要是记录部分匹配值的位置
(2)这样就又有AB部分匹配,所以下次得后移两位开始重新匹配
(3)
代码:
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;
}
}
上一篇: PAT_A1006 | Sign In and Sign Out
下一篇: 字符串之KMP详解