有关KMP算法
菠菜面筋 人气:1
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/articlehttps://img.qb5200.com/download-x/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 }
加载全部内容