算法流程：
kmp_search(char[] text,char[] pattern)
构建前缀表
prefix[0]默认为0
i从1开始遍历pattern
pattern[i]==pattern[len]时，采用的策略
len++;//最长公共前缀+1
prefix[i]=len;//记录当前i位置的前缀
i++;//向后移动1位
pattern[i]!=pattern[len]时，采用的策略
如果前缀值>0 ,则向左下移动
len=prefix[len-1];
如果前缀值<=0,则记录前缀值，并右移 prefix[i]="len;//len其实就是0" i++; < code></=0,则记录前缀值，并右移>
KMP搜索
看代码吧..
完整KMP
public class Kmp {
/*
*@func 构建前缀表
*@param pattern:匹配字符数组,prefix：前缀表,n匹配字符数据的长度
*/
public static void prefix_table(char[] pattern,int[] prefix,int n){
prefix[0] =0;//前缀表第一个初始为0
int len =0;//len为前缀值，从0开始
int i =1;//从第一个开始
while(i<n){ if(pattern[i]="=pattern[len]){//当前字符与前缀值相同" len++; prefix[i]="len;" i++; }else{ 当前字符与前缀值相同不同 if(len>0)
len=prefix[len-1];//左下移动，直到前缀值等于0
else{
prefix[i]=len;//前缀值为0,赋值给当前i的前缀值
i++;//i右移
}
}
}
}
/*
*@func 完成前缀表的构建
*/
public static void move_table(int[] prefix){
int len=prefix.length;
for(int i=len-1;i>0;i--)
{
prefix[i]=prefix[i-1];
}
prefix[0]=-1;
}
public static void kmp_search(char[] text,char[] pattern){
int n=text.length;//n =text的长度
int m=pattern.length;//m=pattern的长度
int i=0;//遍历text
int j=0;//遍历pattern
//构建前缀表
int [] prefix=new int[m];
prefix_table(pattern,prefix,m);
move_table(prefix);
while(i<n){ 遍历text if(j="=m-1&&text[i]==pattern[j])//当匹配到最后一个字符时" { system.out.println("found："+(i-j)); j="prefix[j];//继续向后匹配" } if(text[i]="=" pattern[j]) 对比相同 i++; j++; }else 对比不相同 public static void main(string[] args) string text="ABABABCABAABABCABAA" ; pattern="ABABCABAA" kmp_search(text.tochararray(), pattern.tochararray()); < code></n){></n){>
参考文献：
https://www.bilibili.com/video/BV1Px411z7Yo/?spm_id_from=333.788.recommend_more_video.-1 —-KMP字符串匹配算法1
https://www.bilibili.com/video/BV1hW411a7ys/?spm_id_from=333.788.recommend_more_video.0 —-KMP字符串匹配算法2
Original: https://www.cnblogs.com/alexanders/p/16284318.html
Author: AlexanderOscar
Title: Kmp算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/643196/
转载文章受原作者版权保护。转载请注明原作者出处！