一个简易的kmp教学并给出java实现

简单介绍一下问题

给定source字符串,找出target字符串出现的首位

例如

source   为“abddabddabc”

target  为 “abddabc”

从第一位开始比较 |a b d d a b|d d a b c

         |a b d d a b|c   不匹配

从第二位继续比较 a|b d d a b d d a b c

           |a       不匹配

。。。

。。。

从第五位继续比较 a b d d|a b d d a b c

             a b d d a b c  匹配成功

再给出kmp算法

从第一位开始比较 a b d d a b|d d a b c

         a b d d a b|c  不匹配

————————————————————————————————

观察失配处前两位ab与target的前两位ab一致,

而整个target不再出现ab,所以即使出现匹配,也只能出现在最后两位

也就是ab之后,所以我们可以直接跳过中间所有位

直接把target的前两位与source当前ab对齐,继续匹配

————————————————————————————————

第二次匹配        a b d d| a b|| d d a b c 

                   | a b||d d a b c 

其中单斜杠处即为所求 双斜杠处为第二次匹配起始位

在上个例子 两条长横线中的内容就是kmp的核心思路:

不需要每一次失配都只从下一位继续,

只需要对比首位的重合部分,移动target,使其首尾重合部分对其,即可继续对比

再举一个极端的例子,便于理解

target 为 abcdefgh

如果source存在匹配部分,那这部分必由a起始

所以在匹配的过程中,发生了失配,即可全部跳过,对比下一位是否为a

而对于首尾有重合部分,则需要从重合部分下一位开始,而重合部分的起始位即为所求

重新用自然语言描述一下我们要做的事:

1  开始匹配 如果完成匹配 返回重合的起始位

2  发生失配 从当前失配位 观察target的首尾重合部分

3     调整target到重合部分首位 从失配位继续匹配

而失配位前target的首尾重合部分的长度由target自身决定,举例说明

  a b d d a b d d a b c

  0 1 2 3 4 5 6 7 8 9 10

  0 0 0 0 1 2 3 4 1 2 0

比如当source为

  a b d d a b d d c c c c c c c c c

  0 1 2 3 4 5 6 7 8 9 10

  0 0 0 0 1 2 3 4 1 2 0

a b d d a b d d a b c

我们在第八位发生失配,那么在0+8-4位为起始,从target的4 位继续匹配即可

下面给出java代码实现:

package cn.baqn.selfstudy;
public class Solution {
 public static void main(String[] args) {
  String source="abddabkdabc";
  String target="abddabc";
  int a=Solution.strStr(source, target);
  System.out.println(a);
 }
 public static int strStr(String source, String target) {
  if(target=="") {
   return 0;
  }
  if(source.length()<target.length()) {
   return -1;
  }
  int[] next=nextKmp(target);
  int j=0;
  int i=0;
  while(true){
   while(j<target.length()&&(i+j)<source.length()&&source.charAt(i+j)==target.charAt(0+j)) {
    //System.out.println(source.charAt(i+j));
    j++;
   }
   if(j==target.length()) {
    System.out.println("!");
    return i;
   }
   if((i+j)==source.length()) {
    return -1;
   }
   if(j==0) {
    i++;
    continue;
   }
   i=i+j-next[j-1];
   j=next[j-1];
   
   
  }
    }
 public static int[] nextKmp(String str) {
  if(str.equals("")) {
   return null;
  }
  int[] next=new int[str.length()];
  for (int i = 0; i < next.length; i++) {
   next[i]=0;
  }
  for (int i = 1; i < str.length(); ) {
   int j=0;
   while((i+j)<str.length()&&str.charAt(i+j)==str.charAt(0+j)) {
    next[i+j]=j+1;
    j++;
   }
   if(j==0) {
    i++;
   }else {
    i+=j; 
   }
  }
  return next;
 }
}

    

上一篇:docker-compose docker启动工具,容器互联


下一篇:Docker 启动时容器无法联网