怎么在java项目中实现一个KMP算法？针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
KMP算法是一种神奇的字符串匹配算法，在对 超长字符串 进行模板匹配的时候比暴力匹配法的效率会高不少。接下来我们从思路入手理解KMP算法。
在对字符串进行匹配的时候我们最容易想到的就是一个个匹配，类似下面这种：
换成Java代码就是：
public static boolean bfSearch(String pattern,String txt){
if (txt.length() < pattern.length())
return false;
for (int i = 0; i < txt.length(); i++) {
boolean flag = false;
for (int j = 0; j < pattern.length(); j++) {
if (i+j>=txt.length())
return false;
if (txt.charAt(i+j)!=pattern.charAt(j)){
flag = true;
}
}
if (!flag){
return true;
}
}
return false;
}暴力匹配算法的时间复杂度为O(n*m)，n为模板字符串，m为目标字符串，在处理复杂字符串时毫无疑问效率会非常低，由此诞生了KMP算法（时间复杂度为O(m+n) )。
以上面gif图中的两个字符串
txt = “aaacaaab”
pat = “aaab”
为例我们来说一下KMP算法的思路。个人能力有限，您可以先行观看此视频去简单学习KMP的基本原理。
简单原理：构建状态转移数组，当遇到无法匹配的字符时根据状态转移数组进行回溯，以达到减少遍历次数的目的。
对匹配模式字符串进行遍历
从左向右遍历，如果 i 和 j（见源码）所指向的元素相同，则将此状态（j所指向的元素位置）进行保存
最后保存的数组是一个Int类型的状态码数组，每个元素的含义是回溯时模板字符串（pattern）的状态。
对目标字符串进行遍历，检索相同的字符元素。
如果遇到不同的字符元素，根据 J（模板字符串的指针）所在的位置依靠状态转移数组来回溯遍历状态。并在回溯后继续进行匹配。
import java.util.Arrays;
public class KMP {
private int[] patArray; // 状态转移数组
private final String pattern;// 匹配模式字符串
public static boolean bfSearch(String pattern,String txt){
if (txt.length() < pattern.length())return false;
for (int i = 0; i < txt.length(); i++) {
boolean flag = false;
for (int j = 0; j < pattern.length(); j++) {
if (i+j>=txt.length())return false;
if (txt.charAt(i+j)!=pattern.charAt(j)){
flag = true;
}
}
if (!flag){
return true;
}
}
return false;
}
KMP(String pat) { // 通过匹配模式字符串构建对象
this.pattern = pat;
patArray = new int[pattern.length()]; // 创建状态转移数组
int j = 0;
for (int i = 1; i < pattern.length(); ) {
if (pattern.charAt(i) == pattern.charAt(j)){
// 如果i和j指向的字符相同，则将此状态进行保存
patArray[i++] = ++j; // 保存的同时移步下一位
}else {
// 如果 i 和 j 指向的字符不相同，则保持i不动，回溯j
// 如果回溯后的j指向的字符与i相同，则将此时的状态进行保存
if (j <= pattern.length() - 1 && j >0) {
j=patArray[--j]; // 回溯j
if (pattern.charAt(i) == pattern.charAt(j)) {
// 如果回溯后相同，则保存状态
patArray[i++] = ++j;
}
}else if (j == 0) {
// 如果回溯到头，则保存为0状态
patArray[++i] = 0;
}
}
}
}
boolean search(String txt){
int j = 0;
for (int i = 0; i < txt.length(); i++) {
// 对输入的字符串进行模式匹配
if (txt.charAt(i) != pattern.charAt(j)){
// 如果匹配不成功，则根据状态数组对j进行状态更改
if (j>0)--j; // 回溯
j = patArray[j];
}else {
++j; // 匹配成功则进入下一个状态
}
if (j == pattern.length()-1){ // 如果成功匹配，返回true
return true;
}
}
return false;// 匹配不成功
}
}后续的一些思考：
在对比较短的目标字符串而言，毫无疑问使用暴力法的效率（时间复杂度为O（M*N）会快一点，而当目标字符串的长度非常长以后，暴力匹配的效率就会大打折扣。
对于非常长的字符串来说，KMP的O(M+N)的效率相对来说就会非常高。
关于怎么在java项目中实现一个KMP算法问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注创新互联行业资讯频道了解更多相关知识。
