有关KMP算法

husai 2020-03-21 原文

KMP算法：

此算法的本质是首先对于模板字符串进行计算，生成一个数组(next数组)，该数组反映了模板字符串的情况。

例：

S:　　ABADACABABCD

P:　　ABAB

当我们查询道P3与S3(B和D)不相等时，如果是暴力算法，则在从第二个字符开始比较。

而KMP算法则是从P3开始比较(这里的P3只是根据上面举个例子，生成的next数组就是为了找到每一次如果失败后P3的位置，也就是

失配时，模式串向右移动的位数为：失配字符所在位置 – 失配字符对应的next 值)

通过数组再进行查找，以达到降低时间复杂度的目的。

next数组：

{next数组与最大长度值的关系：next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。}

本文具体是在理解KMP算法后的回顾，如果要看详解点击下方连接(讲解的十分清楚)：

原文链接：https://blog.csdn.net/v_july_v/article/details/7041827

下面是具体用java实现的例子：

 1 public class kmp {
 2     
 3     private String ts;
 4     private String ps;
 5     kmp(){
 6     }
 7     kmp(String ts,String ps){
 8         this.ts=ts;
 9         this.ps=ps;
10     }
11     public void setts(String ts){
12         this.ts=ts;
13     }
14     public void setps(String ps){
15         this.ps=ps;
16     }
17     public int kmpmatch() {                    //KMP开始运算
18         int slen=ts.length();
19         int plen=ps.length();
20         int i=0;
21         int j=0;
22         int[] next =getNext(ps);
23         while(i<slen&&j<plen) {
24             if(j==-1||ts.charAt(i)==ps.charAt(j)) {
25                 i++;
26                 j++;
27             }else {
28                 j=next[j];
29             }
30         }
31         if(j==plen) {
32             return i-j;
33         }else {
34             return -1;
35         }
36         
37     }
38     public int[] getNext(String ps) {
39     char[] p =ps.toCharArray();
40     int[] next = new int[p.length];
41     next[0]=-1;
42     int j=0;
43     int k=-1;
44     while(j<p.length-1) {                    //此算法的精髓！！！！！
45         if(k==-1||p[j]==p[k]) {
46             k++;
47             j++;
48             if(p[j]!=p[k]) {
49                 next[j]=k;
50             }else {
51                 next[j]=next[k];
52             }
53         }else {
54             k=next[k];
55         }
56     }
57         return next;
58     }
59 
60 
61 
62     public static void main(String[] args) {
63         // TODO Auto-generated method stub
64         String A = "wdnmwdnmwdnmddnm";
65         String B = "wdnmwdnmd";
66         kmp k =new kmp();
67         k.setts(A);
68         k.setps(B);
69         System.out.println(k.kmpmatch());        //输出的4
70     }
71 
72 }