KMP

1.发现问题

给定一个字符串s1 “aaaaaab”，以及一个模式字符串s2 “aaab”，如果要判断字符串2是否是字符串1的子串，即两个字符串是否匹配，正常情况下，我们会挨个比较，比如先判断s1[0]==s2[0]，然后判断s1[1]==s2[1]，然后是s1[2]==s2[2]，然后是s1[3]!=s2[3]，所以我们会从s1的第二个位置为起始位置，重新开始比较，即s1[1] == s2[0], s1[2]==s2[1], s1[3]==s2[2], s1[4]!=s2[3]，然后会从s1的第三个位置为起始位置开始比较，……..，最终，时间复杂度是O(mn)，m是s1的长度，n是s2的长度。

2.找到规律

上面这个例子我们可以发现，字符串的某些部分被重复比较了很多次，每次失败都是重头开始。我们发现其实只需要比较部分字符串即可，那些前缀后缀相等的字符就不用比较了。比如acbacx..和acbaca...，比较到字符x和字符a时，不相等，按照我们前缀和后缀相等，就直接跳过前缀，直接比较后缀。即直接从串1的x字符和串2的b字符开始比较，即比较acx...和acbaca...

3.如何求最长前缀后缀数组

前缀后缀数组的特点是前缀和后缀的字符相等，比如acbac的前缀后缀是ac，所以这个字符的最长前缀后缀就是ac。所以每个数组元素的值就是以当前位置index对应字符结尾的字符串的最长前缀后缀的长度。

比如acbac的最长前缀后缀数组为[0,0,0,1,2] (index=0位置默认为0)

private int[] computeTemporaryArray(char pattern[]){
    int [] lps = new int[pattern.length];
    int index =0;
    for(int i=1; i < pattern.length;){
        if(pattern[i] == pattern[index]){
            lps[i] = index + 1;
            index++;
            i++;
        }else{
            if(index != 0){
                index = lps[index-1];
            }else{
                lps[i] =0;
                i++;
            }
        }
    }
    return lps;
}

4.KMP算法

利用前缀后缀数组，避免当不匹配时重新从模式字符串的头部开始匹配，也避免了从给定字符串的匹配位置的下一个位置开始。时间复杂度是O(m+n)

public boolean KMP(char []text, char []pattern){

    int lps[] = computeTemporaryArray(pattern);
    int i=0;
    int j=0;
    while(i < text.length && j < pattern.length){
        if(text[i] == pattern[j]){
            i++;
            j++;
        }else{
            if(j!=0){
                j = lps[j-1];
            }else{
                i++;
            }
        }
    }
    if(j == pattern.length){
        return true;
    }
    return false;
}