KMP算法（子字符串快速匹配算法）

KMP

• 求一个字符串是不是另一个字符串子串的问题
• 暴力方法是O(N*M)的复杂度

  最长前缀和后缀的匹配长度

• 一个字符位置存储的信息是匹配长度
• 
  • 上图中前缀从最左算起，后缀从最右算起，等于3的时候相等
  • 将这个信息记录在K这个字符的位置
  • 这个长度必须小于整体的长度
• 以上这个信息需要对str2（也就是较短的字符串）求的
  • 
  • 第一个是-1是人为定义的

    加速过程

• 
  • 当长字符串的匹配进行到x位置的时候发现匹配不能继续，假如此时短字符串的匹配进行到了y位置，那么不需要回退x，只需要回退y到最长前缀的末尾位置（图中画框的位置），相当于不需要从头开始匹配，而是从图上的j位置（下标三角）开始，只需要通过最长前缀和后缀跳过长字符串和短字符串中已经匹配过的段，实际上相当于将短字符串直接后移到最长前缀的位置，然后继续匹配即可。
  • 另一个问题是从i到j位置之间不可能有任何一个位置能够配出短字符串
• 举例
• 
  • 团上的行为是先从两个字符串的头位置开始比对两个字符串，然后到第一个字符串的e位置发现不对，然后寻找此时短字符串的w位置的最长前缀位置的下一个位置也就是t，但是t于e仍然不相等，那么就寻找t位置的最长前缀的下一个位置，也就是s与e比较，但是还不相等，那么就选择s位置的最长前缀的下一个位置是短字符串的开始位置，也不行，此时将长字符串的比较位置后移一位到e的下一个位置，重新开始比较

    如何求

    void getNext (int* next, const string& s)
    {
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++)
        {
            while(j > 0 && s[i] != s[j]) 
            {
                j = next[j - 1];
            }
            if(s[i] == s[j]) 
            {
                j++;
            }
            next[i] = j;
        }
    }

• j指向的是前缀末尾位置，初始化为0
• i是后缀末尾位置，初始化为1
• next数组第一个位置也初始化为0
• 如果i和j位置的字母不相等，那么j开始回退到上一个位置的前缀结束位置（相当于前缀长度减少了1）
  • 直到前缀和后缀字母相同的位置
• 此时如果前后缀的最后一个位置字母相同，则给j的大小+1，因为相同的话后缀长度+1
• 然后将这个值赋给i位置（也就是当前后缀得末尾位置），记录下到这个位置的最长后缀长度

Leetcode 28. 找出字符串中第一个匹配项的下标

• 讲解
• 注意比较的时候
  • 如果二者不相等，needle就按照当前不匹配位置的前一个位置的next表持续回退到起始或者相等，使得前缀来到原来后缀的位置
  • 如果相等，就二者一起前进一位
  • 如果到达了needle的末尾，就认为是匹配到了，返回位置

    class Solution {
    public:
        void getNext(int* next, const string& s) {
            int j = 0;
            next[0] = 0;
            for(int i = 1; i < s.size(); i++) {
                while (j > 0 && s[i] != s[j]) {
                    j = next[j - 1];
                }
                if (s[i] == s[j]) {
                    j++;
                }
                next[i] = j;
            }
        }
        int strStr(string haystack, string needle) 
        {
            if (needle.size() == 0) 
            {
                return 0;
            }
            int next[needle.size()];
            getNext(next, needle);
            int j = 0;
            for (int i = 0; i < haystack.size(); i++) 
            {
                while(j > 0 && haystack[i] != needle[j]) {
                    j = next[j - 1];
                }
                if (haystack[i] == needle[j]) {
                    j++;
                }
                if (j == needle.size() ) {
                    return (i - needle.size() + 1);
                }
            }
            return -1;
        }
    };