您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

KMP算法解决字符传匹配(图文)

第十三双眼睛2023-10-22【数据结构与算法】人已围观

简介KMP算法解决字符传匹配

KMP算法解决字符传匹配

package com.xingchen.day016;
import java.util.Arrays;
public class KMP {
public static void main(String[] args) {
String s1 = "BBC ABCDAB ABCDABCDABDE";
String s2 = "ABCDABD";
int[] next = kmpNext("ABCDABD");
int search = kmpSearch(s1, s2, next);
//System.out.println(Arrays.toString(next));
System.out.println(search);
}
public static int kmpSearch(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 dest) {
//创建一个数组，保存部分匹配值
int[] next = new int[dest.length()];
next[0] = 0;//如果字符串的长度为1，则部分匹配值就是0
for (int i=1, j= 0 ; i<dest.length(); i++) {
//当charAt(i)不等于charAt(j)时，需要从next中获取新的j
//直到charAt(i)等于charAt(j)时退出
while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j-1];
}
// charAt(i)等于charAt(j)时
if (dest.charAt(i) == dest.charAt(j)) {
j ++;
}
next[i] = j;
}
return next;
}
}

Tags：

很赞哦！ ()

上一篇：字符串暴力匹配(图文)

下一篇：贪心算法(图文)