写在前面,本人水平低,文章仅供自己参考

高水平文章和视频请参考:28. 找出字符串中第一个匹配项的下标题解:【宫水三叶】简单题学 KMP 算法

帮你把KMP算法学个通透！（理论篇）_哔哩哔哩_bilibili

帮你把KMP算法学个通透！（求next数组代码篇）_哔哩哔哩_bilibili

1.字符串匹配朴素的算法

        对于字符串匹配的解法,朴素的算法就是从原串s的起始位置开始匹配,匹配串p也从起始位置开始

匹配成功,则s和p一起右移再匹配.

匹配失败,则从上次s开始匹配的下一个位置,与p的起始位置匹配.

例如s: aabaabaaf, p: aabaaf,i表示当前s的匹配位置,start为开始匹配的位置,j表示当前p的匹配位置

一开始start = 0, i = start, j = 0,一直匹配到 i = 5, j = 5时不匹配,start = start +1,  i 从1开始,j重新置为0,再次匹配,这种算法的时间复杂度是O(mn) n为s的长度,m为p的长度.

而kmp算法能做到在(m + n)的时间复杂度下完成匹配,它是如何实现的呢?

2.kmp

        1.首先我们要了解前缀和后缀

        前缀:不包含最后一个字符,包含第一个字符的子串,对于aabaaf, a,aa,aab,aaba,aabaa都是前缀.

        后缀:包含最后一个字符,不包含第一个字符的子串,对于aabaaf, f,af,aaf,baaf,abaaf都是后缀

       2.kmp如何完成

        使用kmp算法时,当发生不匹配时,我们可以观察i从下标0~2开始的字符串都不能匹配上,我们能不能直接跳过这些下标呢?当然是可以的,这也是kmp算法关键,当一个字符串的有相等的前后缀时,我们就不需要再从起始位置的下一个再开始匹配.

        例如,s: aabaabaaf, p: aabaaf,i = 5, j = 5时发生不匹配j位置之前的的字符串aabaa存在相等的前后缀aa,我们从相等前后缀之后开始匹配,即i = 5, j = 2.你会发现i不回退,即对于原串处理的时间复杂度为O(n).j跳转到下一个匹配点的这个过程和原串没有关系,例如不管原串是aabaacaaf,aabaajkjkaaf,j=5时都不匹配,j都是跳转到j = 2,仅与匹配串相关,所以我们只需要找出匹配串每个位置的跳转位置即可,一般将这些数保存在next数组.

        3.next数组生成

        next数组的构造过程,next[i]表示下标为i时的最长相等前后缀,由前后缀的定义可知,当字符串长度为1时没有前后缀的概念,初始化next[0] = 0,i = 1, j = 0,i表示后缀的结尾,j为前缀结尾

        当p[i] = p[j],有相等的前后缀, j++, 

        当p[i] != p[j],j就指向前一个位置的next数组所对应的值,即j = next[ j - 1],循环进行,直至p[i] = p[j] 或者 j = 0, 如果j = 0, 仍有p[i] != p[j],则next[i] = 0,i往后移动,j不变.这个过程其实是在不断的减小前后缀的长度看是否有相等的,比如aabaaf当 j = 2时, i = 5时不匹配就是前缀aab和后缀aaf不匹配,j跳到next[j - 1] = 1,发现aa和af还不匹配就继续,如果j = 5时p[i] = a,当j跳到next[j - 1] = 1时,就有相等的前后缀

        直到遍历完匹配串p,获得next数组

4.与原串的匹配过程

        最后就是完成从原串中查找匹配串,其过程和寻找next数组极其相似

1. 匹配成功,则j++
2.  匹配不成功,则j跳转到next[j - 1],直至s[i] = p[j] 或者 j = 0
3. i++
4. 结束条件是j = m,即匹配完成p,在原串中找到了p, 返回 i - m + 1,即p串在原串s的起始位置

   实现代码(写在leetcode上的) 

class Solution {

    public int strStr(String haystack, String needle) {
        int n = haystack.length(),m = needle.length();
        int[] next = new int[m];//仅与匹配串相关

        char[] s = haystack.toCharArray();
        char[] p = needle.toCharArray();

        //构造next数组
        findNext(next,p);

        //匹配过程
        for(int i = 0, j = 0; i < n; i++){
            //匹配失败 j跳转到 next[j - 1] 直至 s[i] = p[j] 或者 j = 0
            while(j > 0 && s[i] != p[j]) j = next[j - 1];
            //匹配成功 j++
            if(s[i] == p[j]) j++;
            //如果j为p的长度m 则在原串s中找到了p 返回下标
            if(j == m) return i - m + 1;

        }

        return -1;
    }
    //p: 匹配串
    public void findNext(int[] next,char[] p){
        //构造next数组 i为当前子串长度 j为前缀结尾
        for(int i = 1, j = 0; i < p.length; i++){
            //不匹配 j跳转到 next[j - 1] 直到 p[i] = p[j] 或者 j = 0
            while(j > 0 && p[i] != p[j]) j = next[j - 1];
            //匹配 j加1
            if(p[i] == p[j]) j++;
            //记录当前最长相等前后缀的长度
            next[i] = j;
        }
    }

}