KMP匹配算法代码实现

首页 » 算法 » KMP匹配算法代码实现

目前我看到讲的比较好理解的视频是这两个,

https://www.bilibili.com/video/BV1jb411V78H?from=search&seid=3885756804092911843

https://www.bilibili.com/video/BV1Px411z7Yo?from=search&seid=3885756804092911843

有需要可以看看,下面是一个测试,(笔记)

package 十大算法;

import java.util.Arrays;

public class KMP {
public static void main(String[] args) {
 String str1="bbc abcdab abcdabcdabde";
 String str2="abcdabd";
 int[]next=kmpnext("abcdabd");
 int index=kmpsearch(str1, str2, next);
 System.out.println(index);
}
//kmp搜索算法
/**
 * 
 * @param str1 源字符串
 * @param str2 字串
 * @param next 部分匹配表,是字串对应的部分匹配表
 * @return 如果是-1就是没有匹配到,否则返回第一个匹配的位置
 */
public static int kmpsearch(String str1,String str2,int []next) {
 for(int i=0,j=0;i<str1.length();i++) {
  //当str1.charAt(i)!=str2.charAt(j),去调整j的大小
  //移动位数=已匹配的字符数-对应的部分匹配值
  while(j>0 && str1.charAt(i)!=str2.charAt(j)) {
   j=next[j-1];
  }
  if(str1.charAt(i)==str2.charAt(j)) {
   j++;
  }
  if(j==str2.length()) {
   //找到
   return i-j+1;
  }
 }
 return -1;
}
//获取到一个字符串(字串)的部分匹配值表
public static int[]kmpnext(String dest){
 //创建一个next数组保存部分匹配值
 int []next=new int[dest.length()];
 next[0]=0;//如果字符串的长度为1,部分匹配值就是0
 for(int i=1,j=0;i<dest.length();i++) {
  //当dest.charAt(i)!=dest.charAt(j),需要从next[j-1]获取新的j
  //直到发现有dest.charAt(i)==dest.charAt(j)成立才退出
  while(j>0&&dest.charAt(i)!=dest.charAt(j)) {
   j=next[j-1];
  }
  //当dest.charAt(i)==dest.charAt(j)满足时,部分匹配值就是+1
  if(dest.charAt(i)==dest.charAt(j)) {
   j++;
  }
  next[i]=j;
 }
 return next;
}
}
分享到:
赞(1) 打赏

评论 2

评论前必须登录!

 

  1. #1

    我也是学计算机的

    笔记本6个月前 (05-26)
  2. #2

    good厉害了

    沥青6个月前 (05-26)

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00