kmp解决字符串算法
2022/2/15 11:41:52
本文主要是介绍kmp解决字符串算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
package com.zou.Algorithm.kmp; import java.util.Arrays; public class KmpAlgorithm { public static void main(String[] args) { String str1="BBC ABCDAB ABCDABCDABDE"; String str2="ABCDABD"; int[] next=kmpNext("ABCDABD"); System.out.println("next="+ Arrays.toString(next)); int index=kmpSearch(str1,str2,next); System.out.println("index="+index); } //搜索算法 public static int kmpSearch(String str1,String str2,int[] next){//next匹配表 for (int i = 0,j=0; i < str1.length(); i++) { 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[]从新获取 //直到成立dest.charAt(i)==dest.charAt(j)退出 while(j>0&&dest.charAt(i)!=dest.charAt(j)){ j=next[j-1];//核心 } if (dest.charAt(i)==dest.charAt(j)){ j++; } next[i]=j; } return next; } }
这篇关于kmp解决字符串算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08如何在敏捷项目中实现高效测试?
- 2024-07-08用户故事一定要有 “So that...” 吗?
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt