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

题目来源

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

题目解析

暴力解法

本题如果采用暴力解法的话，可以定义两个指针 i，j，其中 i 指针用于扫描 S（haystack）串，j 指针用于扫描 T（needle）串。

比如：S = "aabaabaaf"，T = "aabaaf"

假设 S 串的起始匹配位置为 k，则 k 取值范围是：[0, s.length - t.length]

上图匹配过程中，分为两个循环：

外层循环，即匹配的轮数控制，或者说是，S串的匹配起始位置控制，比如：

• 第 0 轮，T 串是从 S 串的 0 索引位置开始匹配
• 第 1 轮，T 串是从 S 串的 1 索引位置开始匹配
• ...
• 第 k 轮，T 串是从 S 串的 k 索引位置开始匹配

内层循环，即T串和S串的 k ~ k + t.length 范围进行逐个字符一一匹配，

• 如果发现存在对应位的字符不一致，则说明当前轮匹配失败，直接进入下一轮
• 如果所有位置上的字符都相同，则说明匹配成功，即在S中找到了和T相同的子串，且该子串起始位置是k

假设，s.length = n，t.length = m，则暴力解法的时间复杂度为O(n * m)

KMP算法

对于字符串模式匹配问题，暴力算法并非最优解决方案，虽然 s，t 都是随机串，但是这些随机串也会存在一定规律可以利用。

比如上面暴力解法图示中，当第 k = 0 轮匹配失败后，第 k =1 轮，第 k =2 轮是否注定失败了呢？

如下图是第 k = 0 轮最后一个字符匹配失败的情况：

我们观察其中匹配成功的部分，即"aabaa"部分，这部分具有相同前后缀aa。

如果我们将 S，T 的 "aabaa" 后面部分抽象化（....），如下图所示，那么：

• 第 k = 0 轮匹配失败是因为 “抽象部分（....）” 的匹配失败
  
  
• 第 k = 1 轮，第 k = 2 轮匹配失败，其实就是 "aabaa" 部分的匹配失败：
  
  

 我们将第 k = 1 轮，第 k = 2 轮，第 k = 3 轮再次简化一下，如下图所示：

那么是不是很显然可以发现，第1轮，第2轮是注定失败的。

我们再举一个例子：

如果上面 S，T 在第 k = 0 轮因为抽象部分（...）匹配失败，那么下一轮，其实是否可以直接让：前缀部分直接跳转到后缀位置？

因为前缀部分（如abc）和后缀部分（如abc）完全相同，而前缀部分（如abc）和中间部分（如d）不相同，因此前缀部分（如abc）和中间部分对齐（如d）时，必然匹配失败。

这样的话，是不是跳过了两轮匹配，即节省了两轮匹配的时间。

请大家再思考一下，上面让前缀部分直接跳转和后缀部分对齐，真的是只节省两轮匹配的过程吗？

下面图示是，第0轮匹配失败后，直接跳到对称部分开始重新匹配

如果对应到暴力解法过程的话，那么下面画X的部分就都是跳过的过程

我们再观察下这个跳到对称部分的过程中，i，j指针的变化

可以发现，i 指针在 S 中的位置并没有改变

• j 指针回退指向到了 T 的 "aabaa" 前缀部分（aa）的后一个位置（b所在位置）
• 或者假设前缀部分（aa）长度为 len，则 j 回退到 T 串的 len 索引位置

那么上面这个改进算法的时间复杂度是多少呢？

由于上面算法中，保证了 i 指针不会回退，因此时间复杂度只有O(n)。

而这个算法其实就是KMP算法。

前缀表概念

上面我们已经说明了KMP算法的大致原理，其中最关键的就是在模式串 T 中找其前缀子串的最长相同前后缀，比如

T = "aabaaf" 有前缀子串 "aabaa"，该子串的最长相同前后缀是 "aa"

那么该如何通过代码来实现这个功能呢？

KMP算法的三个创始人K，M，P提出了前缀表的概念。

首先定义下字符串的前缀、后缀概念

假设字符串 t 长度为n，那么：

• 前缀就是起始索引必须为0，结束索引＜n-1的所有子串
• 后缀就是结束索引必须为n-1，起始索引必须>0的所有子串

因此

• 前缀和后缀不能是字符串 t 本身
• 字符串 t 的前缀和后缀是可能存在重叠部分的

我们举一个例子，比如列出T的子串 "aabaa" 的所有的前缀和后缀

其中最长且相同的前后缀是"aa"。

注意，判断前缀和后缀是否相同，都是从左往右逐一比对，因此上面例子中，长度为3的前缀"aab"和后缀"baa"是不相同的。

还有相同的前缀、后缀是可能存在重叠

比如字符串 "ababab"

最长相同的前缀和后缀是"abab" ，他们是存在重叠的

因此T = "aabaaf"所有前缀子串的最长相同的前缀和后缀的长度分别为：

我们将 T 的所有前缀串对应的 “最长相同的前后缀的长度” 记录为一个数组 next，我们称 next 为前缀表

next = [0, 1, 0, 1, 2, 0]

前缀表的应用

前面我们手算出了前缀表 next 数组

next = [0, 1, 0, 1, 2, 0]

next[j] 表示：T 的 [0, j] 范围子串的最长相同前后缀长度，比如：

• next[0] 表示：T的 [0,0] 范围子串 "a"          的最长相同前后缀长度 0
• next[1] 表示：T的 [0,1] 范围子串 "aa"        的最长相同前后缀长度 1
• next[2] 表示：T的 [0,2] 范围子串 "aab"      的最长相同前后缀长度 0
• next[3] 表示：T的 [0,3] 范围子串 "aaba"    的最长相同前后缀长度 1
• next[4] 表示：T的 [0,4] 范围子串 "aabaa"  的最长相同前后缀长度 2
• next[5] 表示：T的 [0,5] 范围子串 "aabaaf" 的最长相同前后缀长度 0

那么如何将 next 应用到KMP算法中呢？

比如下图中，S[i] != T[j] 时，我们前面分析过，需要做如下动作：

• i 指针保持指向不变
• j 指针回退到 T 的 len 索引位置（len：表示 T 的前缀串 "aabaa" 的最长相同前后缀 "aa" 的长度）

len 含义和 next[j-1] 含义是相同的

• next[j - 1] 表示 T 的 [0, j-1] 范围子串 "aabaa" 的最长相同前后缀的长度 

因此，当s[i] != t[j] 时，我们可以让： j = next[ j - 1 ]

另外，如果 j = 0 时就匹配不上，此时 next[j-1] 会发生越界异常，因此针对这种i情况，我们应该特殊处理，如下图所示，就是一个 j = 0无法匹配的情况：

此时，我们应该让 i++，j 保持不变，继续匹配

这其实和前面KMP算法规定的 i 指针不回退这一条件不冲突。因为上面过程 i 指针没有发生回退。

生成前缀表

前面我们已经手算过了前缀表，但是手算过程是一个暴力枚举的过程。

关于前缀表的生成，我们可以利用动态规划求解。

比如：假设已知 K = NEXT[J-1]，现在要求 NEXT[J]，比如下图

如果 T[J] == T[K] 的话，比如

NEXT[J] 表示 [0, J] 范围子串 "abdabeabdabe" 的最长相同前后缀（"abdabe"）长度为 K+1

因此当 T[J] == T[K] 时，那么 NEXT[J]  = K + 1

如果T[J] ! = T[K]的话，比如

那么此时该如何求解 NEXT[J] 呢？

我们将上图继续分解

如果下面两个位置的字符相同

那么此时就找到了 NEXT[J] 的值。

因此当 T[J] != T[K] 时，我们可以让 K = NEXT[K-1]，继续前面逻辑，直到 K 移动到：

• T[J] == T[K] 时，此时 NEXT[J] = K + 1
• 若 K == 0 时，依旧 T[J] != T[K]，则此时可以认为 NEXT[J] = 0，此时我们J++，求解下一个 NEXT[J]

C算法源码

暴力解法

int strStr(char* s, char* t) {
    int sLen = strlen(s);
    int tLen = strlen(t);

    for (int k = 0; k <= sLen - tLen; k++) {
        int i = k;
        int j = 0;

        while (j < tLen && s[i] == t[j]) {
            i++;
            j++;
        }

        if (j == tLen) {
            return k;
        }
    }

    return -1;
}

KMP算法

int* getNext(char* t) {
    int tLen = strlen(t);

    int* next = (int*)calloc(tLen, sizeof(int));

    int j = 1;
    int k = next[j - 1];

    while (j < tLen) {
        if (t[j] == t[k]) {
            next[j] = k + 1; // 前缀范围 t[0,k] == 后缀范围 t[j-k,j]  此时最长相同前后缀长度为：k+1
            j++;
            k++;
        } else if (k > 0) {
            k = next[k - 1]; // 若 t[j] != t[k] && k > 0，则缩短前缀部分，k = next[k-1] 后继续比较 t[k] 和 t[j]
        } else {
            j++; // 若 t[j] != t[k] && k == 0，则 k 无法继续后退，此时可以认为 next[j] 为 0，进行j++，继续求解下一个next[j]
        }
    }

    return next;
}

int strStr(char* s, char* t) {
    int sLen = strlen(s);
    int tLen = strlen(t);

    int* next = getNext(t); // 生成 t 串的前缀表

    int i = 0;
    int j = 0;

    while (i < sLen && j < tLen) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else if (j > 0) {
            j = next[j - 1]; // 若 s[i] != t[j] && j > 0，则 i 指针不动，j 指针回退到 t 串的 next[j-1] 位置 
        } else {
            i++; // 若 s[i] != t[j] && j == 0，则表示 s[i] 和 t[0] 首个字符就匹配失败，我们只能进入下一轮，即 i++
        }
    }

    if (j == tLen) { // 若 t 串所有字符都被匹配成功，则 j == t.length
        return i - j; // 此时 s 串的 i - j 位置就是首次匹配 t 的子串起始位置
    } else {
        return -1;
    }
}

C++算法源码

暴力解法

class Solution {
public:
    int strStr(string s, string t) {
        int sLen = s.size();
        int tLen = t.size();

        for (int k = 0; k <= sLen - tLen; k++) {
            int i = k;
            int j = 0;

            while (j < tLen && s[i] == t[j]) {
                i++;
                j++;
            }

            if (j == tLen) {
                return k;
            }
        }

        return -1;
    }
};

KMP算法

class Solution {
public:
    int strStr(string s, string t) {
        vector<int> next = getNext(t); // 生成 t 串的前缀表

        int i = 0;
        int j = 0;

        while (i < s.size() && j < t.size()) {
            if (s[i] == t[j]) {
                i++;
                j++;
            } else if (j > 0) {
                j = next[j - 1]; // 若 s[i] != t[j] && j > 0，则 i 指针不动，j 指针回退到 t 串的 next[j-1] 位置 
            } else {
                i++; // 若 s[i] != t[j] && j == 0，则表示 s[i] 和 t[0] 首个字符就匹配失败，我们只能进入下一轮，即 i++
            }
        }

        if (j == t.size()) { // 若 t 串所有字符都被匹配成功，则 j == t.length
            return i - j; // 此时 s 串的 i - j 位置就是首次匹配 t 的子串起始位置
        } else {
            return -1;
        }
    }

    vector<int> getNext(string t) {
        vector<int> next(t.size(), 0);

        int j = 1;
        int k = next[j - 1];

        while (j < t.size()) {
            if (t[j] == t[k]) {
                next[j] = k + 1;  // 前缀范围 t[0,k] == 后缀范围 t[j-k,j]  此时最长相同前后缀长度为：k+1
                j++;
                k++;
            } else if (k > 0) {
                k = next[k - 1]; // 若 t[j] != t[k] && k > 0，则缩短前缀部分，k = next[k-1] 后继续比较 t[k] 和 t[j]
            } else {
                j++; // 若 t[j] != t[k] && k == 0，则 k 无法继续后退，此时可以认为 next[j] 为 0，进行j++，继续求解下一个next[j]
            }
        }

        return next;
    }
};

Java算法源码

暴力解法

class Solution {
    public int strStr(String haystack, String needle) {
        char[] s = haystack.toCharArray();
        char[] t = needle.toCharArray();

        for (int k = 0; k <= s.length - t.length; k++) {
            int i = k;
            int j = 0;

            while (j < t.length && s[i] == t[j]) {
                i++;
                j++;
            }

            if (j == t.length) {
                return k;
            }
        }

        return -1;
    }
}

KMP算法

class Solution {
    public int strStr(String haystack, String needle) {
        char[] s = haystack.toCharArray();
        char[] t = needle.toCharArray();

        int[] next = getNext(t); // 生成 t 串的前缀表

        int i = 0;
        int j = 0;

        while (i < s.length && j < t.length) {
            if (s[i] == t[j]) {
                i++;
                j++;
            } else if (j > 0) { // 若 s[i] != t[j] && j > 0，则 i 指针不动，j 指针回退到 t 串的 next[j-1] 位置 
                j = next[j - 1];
            } else { // 若 s[i] != t[j] && j == 0，则表示 s[i] 和 t[0] 首个字符就匹配失败，我们只能进入下一轮，即 i++
                i++;
            }
        }

        if (j == t.length) { // 若 t 串所有字符都被匹配成功，则 j == t.length
            return i - j; // 此时 s 串的 i - j 位置就是首次匹配 t 的子串起始位置
        } else {
            return -1;
        }
    }

    public static int[] getNext(char[] t) {
        int[] next = new int[t.length];

        int j = 1;
        int k = next[j-1];

        while (j < t.length) {
            if (t[j] == t[k]) {
                next[j] = k + 1; // 前缀范围 t[0,k] == 后缀范围 t[j-k,j]  此时最长相同前后缀长度为：k+1
                j++;
                k++;
            } else if (k > 0) { // 若 t[j] != t[k] && k > 0，则缩短前缀部分，k = next[k-1] 后继续比较 t[k] 和 t[j]
                k = next[k - 1];
            } else {
                j++; // 若 t[j] != t[k] && k == 0，则 k 无法继续后退，此时可以认为 next[j] 为 0，进行j++，继续求解下一个next[j]
            }
        }

        return next;
    }
}

Python算法源码

暴力解法

class Solution(object):
    def strStr(self, s, t):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        for k in range(0, len(s) - len(t) + 1):
            i = k
            j = 0

            while j < len(t) and s[i] == t[j]:
                i += 1
                j += 1
            
            if j == len(t):
                return k
        
        return -1
        

KMP算法

def getNext(t):
    next = [0] * len(t)

    j = 1
    k = next[j - 1]

    while j < len(t):
        if t[j] == t[k]:
            next[j] = k + 1  # 前缀范围 t[0,k] == 后缀范围 t[j-k,j]  此时最长相同前后缀长度为：k+1
            j += 1
            k += 1
        elif k > 0:
            k = next[k - 1]  # 若 t[j] != t[k] && k > 0，则缩短前缀部分，k = next[k-1] 后继续比较 t[k] 和 t[j]
        else:
            j += 1  # 若 t[j] != t[k] && k == 0，则 k 无法继续后退，此时可以认为 next[j] 为 0，进行j++，继续求解下一个next[j]
    
    return next

class Solution(object):
    def strStr(self, s, t):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        next = getNext(t)  # 生成 t 串的前缀表

        i, j = 0, 0

        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
                j += 1
            elif j > 0:
                j = next[j - 1]  # 若 s[i] != t[j] && j > 0，则 i 指针不动，j 指针回退到 t 串的 next[j-1] 位置 
            else:
                i += 1  # 若 s[i] != t[j] && j == 0，则表示 s[i] 和 t[0] 首个字符就匹配失败，我们只能进入下一轮，即 i++
        
        if j == len(t):  # 若 t 串所有字符都被匹配成功，则 j == t.length
            return i - j  # 此时 s 串的 i - j 位置就是首次匹配 t 的子串起始位置
        else:
            return -1
        

JavaScript算法源码

暴力解法

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (s, t) {
    for (let k = 0; k <= s.length - t.length; k++) {
        let i = k;
        let j = 0;

        while (j < t.length && s[i] == t[j]) {
            i++;
            j++;
        }

        if (j == t.length) {
            return k;
        }
    }

    return -1;
};

KMP算法

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (s, t) {
    const next = getNext(t); // 生成 t 串的前缀表

    let i = 0;
    let j = 0;

    while (i < s.length && j < t.length) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else if (j > 0) {
            j = next[j - 1]; // 若 s[i] != t[j] && j > 0，则 i 指针不动，j 指针回退到 t 串的 next[j-1] 位置
        } else {
            i++; // 若 s[i] != t[j] && j == 0，则表示 s[i] 和 t[0] 首个字符就匹配失败，我们只能进入下一轮，即 i++
        }
    }

    if (j == t.length) { // 若 t 串所有字符都被匹配成功，则 j == t.length
        return i - j; // 此时 s 串的 i - j 位置就是首次匹配 t 的子串起始位置
    } else {
        return -1;
    }
};

var getNext = function (t) {
    const next = new Array(t.length).fill(0);

    let j = 1;
    let k = next[j - 1];

    while (j < t.length) {
        if (t[j] == t[k]) {
            next[j] = k + 1; // 前缀范围 t[0,k] == 后缀范围 t[j-k,j]  此时最长相同前后缀长度为：k+1
            j++;
            k++;
        } else if (k > 0) {
            k = next[k - 1]; // 若 t[j] != t[k] && k > 0，则缩短前缀部分，k = next[k-1] 后继续比较 t[k] 和 t[j]
        } else {
            j++; // 若 t[j] != t[k] && k == 0，则 k 无法继续后退，此时可以认为 next[j] 为 0，进行j++，继续求解下一个next[j]
        }
    }

    return next;
}