【字符串算法题记录】28. 找出字符串中第一个匹配项的下标——KMP算法

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

题目链接

暴力求解

这一题蛮简单，但是逻辑上容易忽略一些小细节。我一开始想的是从haystack数组的头开始找与needle匹配的第一个字符，然后再顺着看下面连续的字符是否匹配，然后直接返回结果，但是忽略了很重要的一点：haystack中可能有多个字符和needle的第一个字符是一样的，那么我们不能一次匹配就返回判断结果，而是要遍历整个haystack进行判断。

class Solution {
    public:
    int strStr(string haystack, string needle) {
        int j = 0;
        int index = -1;
        for(int i = 0; i < haystack.size(); i++) { 
            if(haystack[i] == needle[j]) {  // 首先在haystack中找到needle的第一个字符
                index = i;  // 并记录第一个匹配字符的下标index
                // 进入循环检查是否接下来每一个字符都是与needle匹配的
                while(haystack[i] == needle[j] && j < needle.size() && i < haystack.size()) {
                    i++;
                    j++;
                }
                if(j == needle.size()) return index; // 如果needle中的字符全检查完了，则是匹配的，返回对应的index
                else return -1; // 如果needle中的字符没有检查完，即不匹配，则返回-1
            }
        }
        return index; // for循环已经结束都没有返回的话，说明haystack中没有匹配字符，则返回-1
    }
};

第二次修改后的如下，但是还是错了，因为我直接用外层的for循环的变量i去做字符串匹配检查，这其中包含了i++指令，更改了i的值，那么会影响到最外层的for循环。

class Solution {
    public:
    int strStr(string haystack, string needle) {
        int index = -1; // index默认值是-1
        for(int i = 0; i < haystack.size(); i++) { 
            int j = 0;
            if(haystack[i] == needle[j]) {  // 首先在haystack中找到与needle匹配的第一个字符
                index = i;  // 并记录第一个匹配字符的下标index
                // 进入循环检查是否接下来每一个字符都是与needle匹配的
                while(haystack[i] == needle[j] && j < needle.size() && i < haystack.size()) {
                    i++;
                    j++; 
                }
                if(j == needle.size()) return index; // 如果needle中的字符全检查完了，则是匹配的，返回对应的index
                else index = -1; // 如果needle中的字符没有检查完，即不匹配，index要恢复默认值
            }
        }
        return index; // for循环已经结束都没有返回的话，说明haystack中没有匹配字符，则返回-1
    }
};

最终正确代码如下：

class Solution {
    public:
    int strStr(string haystack, string needle) {
        int index = -1; // index默认值是-1
        for(int i = 0; i < haystack.size(); i++) { 
            int j = 0;
            if(haystack[i] == needle[j]) {  // 首先在haystack中找到与needle匹配的第一个字符
                index = i;  // 并记录第一个匹配字符的下标index
                int k = i;  // 用k来代替i进行接下来的检查（不然i值被改变会影响最外层的for循环）
                
                // 进入循环检查是否接下来每一个字符都是与needle匹配的
                while(haystack[k] == needle[j] && j < needle.size() && k < haystack.size()) {
                    k++;
                    j++; 
                }
                if(j == needle.size()) return index; // 如果needle中的字符全检查完了，则是匹配的，返回对应的index
                else index = -1; // 如果needle中的字符没有检查完，即不匹配，index要恢复默认值
            }
        }
        return index; // for循环已经结束都没有返回的话，说明haystack中没有匹配字符，则返回-1
    }
};

KMP算法

上面的暴力求解算法不难看出时间复杂度是O(n × m)，而KMP算法可以将效率提高至O(n + m)。那么什么是KMP算法呢？
他的核心思想在于定义一个模式串的前缀表，然后在目标串中依次比对，碰到不匹配的地方，则回退到模式串此处的相同前缀处继续比对，就不必再退回到模式串的开始而从头再来。文字可能比较难以理解，大家可以去看代码随想录中的示例图，非常清晰明了。

首先我们构造模式串的前缀表，注意这里构造的形式不是固定的，有的前缀表初始值为0，有的为-1（整体向右移），看需求与习惯来决定如何构造，但是核心方法是一样的：

• 初始值为0

void getNext(int* next, string& s) {
        int j = 0;
        next[0] = j; // next初始值为0
        for(int i = 1; i < s.size(); i++) {
            while(j >= 1 && s[i]!=s[j]) // 如果当前前后缀不同，j就要退回到与当前s[i]相等的前缀上
                j = next[j-1];
            if(s[i]==s[j]) j++; // 如果当前前后缀相同，则j向前一位，即指到j+1上
            next[i] = j;    // 将当前前缀的长度赋予next[i]
        }
    }

• 初始值为-1

void getNext(int* next, string& s) {
        int j = -1;
        next[0] = j; // next初始值为-1
        for(int i = 1; i < s.size(); i++) {
            while(j >= 0 && s[i]!=s[j+1]) // 如果当前前后缀不同，j就要退回到与当前s[i]相等的前缀上
                j = next[j];
            if(s[i]==s[j+1]) j++; // 如果当前前后缀相同，则j向前一位，即指到j+1上
            next[i] = j;    // 将当前前缀的长度赋予next[i]
        }
    }

然后再利用next数组来匹配。对于初始值为0的前缀表，我们碰到不匹配的地方是跳到next[j-1]处匹配，而初始值为-1的前缀表，我们是跳到next[j]处。

• 初始值为0

int strStr(string haystack, string needle) {
        int* next = new int[needle.size()]; // 初始化next数组
        getNext(next, needle);
        int j = 0; // next数组起始位置是0
        for(int i = 0; i < haystack.size(); i++) {
            while(j >= 1 && haystack[i] != needle[j]) {   // 如果匹配到不相等的，j就要跳回到相等前缀处，即next[j-1]
                j = next[j-1];
            }
            if(haystack[i] == needle[j]) {
                j++;
            }
            if(j == (needle.size())) {
                delete[] next;
                return (i-needle.size()+1);
            }
        }
        delete[] next;
        return -1;

• 初始值为-1

int strStr(string haystack, string needle) {
        int* next = new int[needle.size()]; // 初始化next数组
        getNext(next, needle);
        int j = 0; // next数组起始位置是-1
        for(int i = 0; i < haystack.size(); i++) {
            while(j >= 1 && haystack[i] != needle[j+1]) {   // 如果匹配到不相等的，j就要跳回到相等前缀处，即next[j]
                j = next[j];
            }
            if(haystack[i] == needle[j+1]) {
                j++;
            }
            if(j == (needle.size() - 1)) {
                delete[] next;
                return (i-needle.size()+1);
            }
        }
        delete[] next;
        return -1;