28. 找出字符串中第一个匹配项的下标 (opens new window)

KMP算法next数组

分析：KMP算法核心在于如何求出模板串的next数组。匹配时如果当前模式串i指针元素不相等，将i更新为模式串的next下标继续比较，如果i为-1则匹配串指针移动(说明i=0也就是模式串的头元素也匹配失败)。

next[ i ]表示：当前【0，i-1】已经匹配的情况下，如果第i个字符不能匹配，那么当前匹配串第i个字符应该和第next[ i ]个字符进行比对。

设计next数组的构建算法时，根据算法思路，需要维护一个前缀字符串尾指针q和后缀字符串的尾指针p，此处可以将p指针与搜索时的当前指针合并，具体包括以下步骤：

• 根据当前p指针与q指针的比对结果，来确定next [p+1]的值：
  • 如果p指针和q指针指向的元素相同，则两个指针同时移动，并将next [p+1]设为q+1。
  • 如果当前p指针指向的元素与q指针指向的元素不同，那么将q指针更新为【0，q-1】中最长匹配前缀+1的索引下标，也就是next[q]，从而保证当前p和q指针对于next[p+1]而言，一定都是最长的前后缀字符串的尾元素。
    • q大于零，则继续对比p和q指向的元素。
    • q等于-1，则说明对于当前p+1指针而言，【0，p】之间不存在长度相等的前后缀，因此设置为0。

这里实际上q=next[q]这一步利用了子问题的解，要求出next[ p+1]，那么需要知道【0，p】之间前后缀相等的最大长度，如果当前最长的前缀【0，q】与后缀【p-q，p】的p,q元素不相等时，也就是【0，q-1】都匹配的情况下，应该从这个区间拿哪一个位置的数和p指针元素进行比较？而这个问题的答案很显然就是next【q】的定义。因为q肯定小于p，所以next【q】子问题的解已经被计算过， 故直接取出来进行迭代。

KMP算法复杂度分析

验证KMP算法时间复杂度为O(m+n)，其中m为匹配串的长度，n为模板串的长度。整个KMP流程分为两个步骤：

• 构建next数组，时间复杂度最坏为O(2n)=O(n)
• 匹配串匹配，时间复杂度为O(2m)=O(m)

下面具体讨论为何匹配串的过程最坏时间复杂度为2m，假定匹配串的指针为i，模板串的指针为j。

①如果i和j指针元素相同，那么i++，j++

②如果i和j不相同，那么j指针需要往前跳，并且next【j】=-1,那么i++

③如果i和j不相同，那么j指针需要往前跳，j=next【j】,继续比较i和j指针元素。

显然以上①和②的循环分支次数合并起来就是i指针能够向后移动的次数，也就是匹配串的长度，O(①+②)=m。

现在难点在于，模板串最多会回跳多少次与匹配串指针进行比较？

从上图可以看出，匹配串在下标为10位置触发了模板串指针的回跳，🌟此时匹配串6-9位置的均只被匹配过一次，因为如果6位置被匹配过两次，要么已经完全匹配模板串，要么匹配串指针已经移动另起一个头指针。显然此时的状况都不符合上面两种假设。所以此时6位置匹配复杂度为O(1)。

可以看到位置10这种情况会导致模板串指针达到最大的回跳次数，而这些复杂度O(n)实际上可以分摊到位置6-10匹配的次数。具体来说，匹配串的匹配索引6，7，8，9，10，10，10，10，10，10实际上可以看作为6，6，7，7，8，8，9，9，10，10，也就是O(2n)。而对于索引大于10或者是索引小于6的位置作为“匹配头”，它们在匹配时并不会增加6-10之间的匹配复杂度。(假设5作为匹配头，匹配时会影响到6,7...相当于将整个蓝色虚线框前移，相邻两个蓝色虚线框并不存在相交)

也就是说蓝色方框内的比对复杂度最坏的情况下为O(2n)，观察不难得出，蓝色方框的【起始匹配】是在上述情况②的后一次匹配，而结束位置是在下一次情况②的前一次匹配时机。这也就是为什么蓝色方框是不会相交的。因此整个匹配串最坏情况下的匹配复杂度为O(2*n)+O(2*n)+...+O( 2*(m-k*n) )=O(2*m)=O(m)

构建next复杂度过程同理分析也可以得到时间复杂度为O(n)，因此最终算法复杂度为O(m)+O(n)=O(m+n)

KMP实现

class Solution {
    public int strStr(String haystack, String needle) {
        int[] next =new int[needle.length()];
        build(next,needle);
        int pinx=0,qinx=0;
        while(qinx<needle.length()&&pinx<haystack.length()){
            if(haystack.charAt(pinx)==needle.charAt(qinx)){
                if(qinx==needle.length()-1) return pinx-needle.length()+1;    
                pinx++;
                qinx++;
            }
            else{
                if(next[qinx]==-1){
                    qinx=0;
                    pinx++;
                }
                else{
                    qinx=next[qinx];
                }
            }
        }
        return -1;
    }
    public void build(int[] next,String needle){
        //匹配串的头指针移动
        next[0]=-1;
        int p=0,q=-1;
        while(p<needle.length()-1){
            //q==-1说明【0，p】之间不存在相等的最长前后缀，p+1位置比较时只能从头进行比较。
            if(q==-1||needle.charAt(p)==needle.charAt(q)){
                p++;
                q++;
                next[p]=q;
            }
            //p指针和q指针不相等，那么将q指针的位置前移，找q串中能与p匹配的最大前缀的尾元素
            else{
                q=next[q];
            }
        }
    }
}