java学习笔记（数据结构与算法14） KMP算法解决字符串匹配问题

有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一个子串 str2="ABCDABD"

现在要判断 str1 是否含有 str2,

如果存在，就返回第一次出现的位置,

如果没有，则返回-1

1.总体思路：我们设置两个索引（i，j）来比较str1第i个元素和str2第j个元素是否相等。

（1）如果相等则比较下一个

（2）不相等，则j=next[j]，这里next[j]的含义是“在str2字符串中，标号为j的字符前面的字符有多少和str2这个字符串前面匹配”，也可以说“标号为j的字符和str2这个字符串具有相同的前缀的字符数”，表现出的效果是“上一个和j具有相同前缀的下标”。

（3）还有当j为-1的时候，说明str2中没有可以和str1（这一段）匹配的字符串（从前往后），这时i++，表示这个字符不匹配了，开始匹配下一个，j也++，表示str2需要从头开始匹配。

2.next获取：

（1）我们要将第一个设为-1，方便后面匹配时，找到无法匹配的情况。

（2）然后每个next只需要保存前面具有相同的前缀的长度。

package KMP;

import java.util.Arrays;

public class StringMatch {
    public static void main(String[] args) {
        System.out.println(isHave("BBC ABCDAB ABCDABCDABDE","ABCDABD"));
    }
    public static int isHave(String s,String p){
        int[] next=getNext(p);
        int length1=s.length();
        int length2=p.length();
        int i=0;
        int j=0;
        while(i 
这个算法不太好理，我表述的确实也不太清楚，如果有问题，可以和我私聊讨论。