数据结构java语言kmp_数据结构(java语言描述)模式匹配——ＫＭＰ算法

关于模式匹配算法，ＢＦ是比较号理解的，但是属于暴力匹配，资源浪费太严重。

KMP算法确实比较难懂(ＰＳ：反正我是看了好久才弄明白，可能也是我理解能力太差＝_＝)

下面是我的一些心得。

/yjiyjige/p/3263858.html

这个是我在网上找到的一个网友的帖子，觉得将得很详细，看了之后恍然大悟。

1.原理

ＫＭＰ算法原理就是在主串和子串做匹配的时候，每次遇到不想同的元素即不能继续匹配时，保持主串正在匹配的那个元素不变，至变更子串的元素(向前移动游标)，从而达到减小时间复杂度的目的。即：“利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。”

结合这个帖子：/tangzhengyue/p/4315393.html

我觉得最重要的是这个图要懂：

代码中，ＢＭＰ方法部分相比于ＢＦ算法改动不大，主要是在判断条件上加了一个

当si=tj时，i/j分别加１，继续比较；

当si!=tj时，i值不变，j变为next(j),继续比较。

做比较时有：１．j退回到next[j]时，若si=tj(tnext(j)),则i/j分别加１,继续比较，若si！=tj(tnext(j))，则j退回j=next[next[j]](即退回k=next[j],j=next[k],这是一个递归，直到k=-1,此时next[k]=0,k=1,next[k]=0)；

２．j退回到j=-1时，另主串和子串下标各加１．

分析条件，子串中的元素要进行比较的情况有：如上黄颜色标出的情况，进行综合得：

有代码：

int j=-1;

while(i

if(j==-1||p[i]==s[i]){

i++;j++}

else{

j=next[j];}}

关于j的变化关系由一个next数组来存储。

对整个子串进行遍历：(０<=j

int[] next1=new int[s.length];//next数组初始化

next1[0]=-1;//next数组的第一个元素初始化

int j=0;

int k=-1;//初始化

while(j

{

if(k==-1||s[j]==s[k])//如果s[j]==s[k]或k==-1，则需要移动j,或则做单纯的做i++ j++,然后值j为０，子串从头开始

{

if(s[++j]==s[++k]){

next1[j]=next1[k];

}else{

System.out.println("j："+j);

System.out.println("k："+k);

next1[j]=k;

}

}else{//s[j]==s[k]和k==-1，都不满足，则往更深以层次比较next(k)

//此时s[j]！=s[k]

k=next1[k];//取k结束的串的最长匹配子串

}

总代码：

package exercise;

import java.util.Scanner;

public class KMP {//与ＢＦ算法有四个不同的地方

public static int km(String s1,String s2){

char[] p=s1.toCharArray();

char[] s=s2.toCharArray();

int[] next=getnext(s2);//与ＢＦ算法相比多了一个next[]数组１

for(int l=0;l

System.out.print(next[l]+" ");

}

int i=0;//主串

int j=0;//子串

while(i

if(j==-1||p[i]==s[j]){//j==-1是当主串和子串的第一个元素不等时多了一个j的判断条件２

i++;

j++;

}else{

//与ＢＦ算法不同的是，此时i不在返回，只有j动//ｉ不动 3

j=next[j];//j回到指定位置

//j不是移动到０，而智能的移动到字串中的最长匹配串的结束位置+1 4

}

}//while结束

if(j==s.length){//s.length

return i-j;

}else{

return -1;

}

}

public static int[] getnext(String s2){

char[] s=s2.toCharArray();//将要个生成next数组的子串转换为char数组

int[] next1=new int[s.length];//next数组初始化

next1[0]=-1;//next数组的第一个元素初始化

int j=0;

int k=-1;//初始化

while(j

{

if(k==-1||s[j]==s[k])//如果s[j]==s[k]或k==-1，则需要移动j,或则做单纯的做i++ j++,然后值j为０，子串从头开始

{

if(s[++j]==s[++k]){

next1[j]=next1[k];

}else{

System.out.println("j："+j);

System.out.println("k："+k);

next1[j]=k;

}

}else{//s[j]==s[k]和k==-1，都不满足，则往更深以层次比较next(k)

//此时s[j]！=s[k]

k=next1[k];//取k结束的串的最长匹配子串

}

}

return next1;

}

public static void main(String[] args){

Scanner sc=new Scanner(System.in);

System.out.println("请输入主串：");

String p=sc.nextLine();

System.out.println("请输入子串：");

String s=sc.nextLine();

int i=km(p,s);//静态的方法main()只能调用静态的方法b(),因为静态方法早于对象而创建，

//调用非静态方法时要提前创建对象，非静态方法要等对象创建之后才能被创建

System.out.println("子串在主串中的位置："+i);

}

}结果：

请输入主串：

ababcabdabcabca

请输入子串：

abcabc

j：1

k：0

j：2

k：0

-1 0 0 -1 0 0 子串在主串中的位置：8