KMP算法
2021/9/23 17:12:27
本文主要是介绍KMP算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
KMP算法
暴力解决
-
思路
从左到右一个个匹配,如果这个过程中有某个字符不匹配,就跳回去,重新开始匹配。
我们可以这样初始化:
-
代码
public class KMP { public static int kmp(String a,String b){ char[] arr = a.toCharArray(); char[] brr = b.toCharArray(); for (int i = 0; i < arr.length; i++) { int tmp = i; for (int j = 0; j < brr.length; j++,tmp++) { if(arr[tmp] != brr[j]){ break; } } if((tmp - i) == brr.length){ return tmp - i - 1; } } return -1; } public static void main(String[] args) { String ts = "abcabde"; String ps = "abde"; System.out.println(kmp(ts,ps)); } }
优化(动态规划)
-
思路
备忘录,记录匹配串的最长前缀下标,匹配失败回退时可以退到最佳位置,减少回溯的次数
-
代码
public class KMP { public static int KMP(String ts,String ps){ char[] t = ts.toCharArray(); char[] p = ps.toCharArray(); int i = 0;//主串 int j = 0;//模式串 int[] next = getNext(ps); while (i < t.length && j < p.length){ if(j == -1 || t[i] == p[j]){ i++; j++; }else { j = next[j]; } } return j == p.length ? i - j : -1; } public static int[] getNext(String ps){ char[] p = ps.toCharArray(); int[] next = new int[p.length]; next[0] = -1; int i = 0; int k = -1; while (i < next.length - 1){ if(k == -1 || p[i] == p[k]){ next[++i] = ++k; }else { k = next[k]; } } return next; } public static void main(String[] args) { String ts = "ssssssssssb"; String ps = "abcabcmn"; System.out.println(KMP(ts,ps)); } }
-
参考文章:https://www.cnblogs.com/yjiyjige/p/3263858.html
这篇关于KMP算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现