题解 | #寻找连续任务开始位置#

• 题目考察的知识点 : 字符串匹配，KMP算法
• 题目解答方法的文字分析：

1. 在匹配主串 s 的时候，如果当前字符与模式串中 j 指向的字符不同，则将指针 j 移动到 next[j-1] 中所存储的值处继续匹配，直到找到一个匹配或者 j=0 为止。如果找到了一个匹配，那么就说明主串中存在一个子串和模式串完全匹配。
2. 我们需要将 words 数组拼接成一个模式串 pattern，并在 s 中查找一个子串，其包含 words 数组中的所有字符串，并且按照 words 数组中的顺序出现。因此，我们可以将 words 数组中的所有字符串合并成一个长的字符串 pattern，然后通过 KMP 算法在 s 中查找 pattern。当找到一个匹配之后，我们只需要更新最长子串的开始位置即可

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @param words string字符串一维数组
# @return int整型
#
class Solution:
    def computeNextArray(self, pattern: str) -> List[int]:
        m = len(pattern)
        j = 0
        next = [0] * m

        for i in range(1, m):
            while j > 0 and pattern[i] != pattern[j]:
                j = next[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
            next[i] = j

        return next

    def findLongestSubstring(self, s: str, words: List[str]) -> int:
        # 将所有的单词拼接成一个模式串
        pattern = "".join(words)

        n, m = len(s), len(pattern)
        if n < m:
            return -1

        # 计算模式串的next数组
        next = self.computeNextArray(pattern)

        i, j = 0, 0
        start, maxLength = -1, -1

        while i < n:
            if s[i] == pattern[j]:
                i += 1
                j += 1
            else:
                if j > 0:
                    j = next[j - 1]
                else:
                    i += 1

            if j == m:
                # 找到了一个匹配的子串
                if i - j > maxLength:
                    maxLength = i - j
                    start = i - m
                # 继续寻找下一个匹配位置
                j = next[j - 1]

        return start