简单介绍一下问题
给定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代码实现：
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];
}
}
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;
}
}