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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的知识点主要是字符串匹配和子序列的概念。

比对字符串有经典的算法:

1. 朴素的模式匹配算法（Brute Force）：这是最简单直接的字符串匹配算法。它的思想是从主串的每一个位置开始，与模式串逐个字符比较，如果匹配失败，则将主串的位置右移一位，再次进行比较，直到找到匹配的子串或者主串被遍历完。这种算法的时间复杂度为O(n * m)，其中n为主串长度，m为模式串长度。
2. KMP算法（Knuth-Morris-Pratt）：KMP算法是一种高效的字符串匹配算法，它通过预处理模式串，得到一个部分匹配表（Partial Match Table），然后利用这个表在匹配过程中尽可能减少比较次数。这种算法的时间复杂度为O(n + m)，其中n为主串长度，m为模式串长度。

题目解答方法的文字分析

本题要求我们在给定的字符串 s 中找到满足一定条件的最长连续子串的开始位置。子串必须按照任务名称在 words 中出现的顺序组成一个子序列。

为了解决这个问题，我们可以使用KMP算法来加速字符串匹配过程。首先，我们将 words 中的所有字符串拼接成一个模式串 pattern。然后，我们使用KMP算法在主串 s 中匹配模式串 pattern，找到满足条件的最长连续子串的开始位置。

在匹配过程中，我们使用KMP算法维护两个指针 i 和 j，分别指向主串和模式串的当前位置。如果当前字符匹配，则同时向后移动两个指针；如果不匹配，则根据模式串的next数组调整模式串指针 j。

当模式串指针 j 指向模式串的末尾时，表示在主串中找到了一个满足条件的子串，此时我们可以记录该子串的开始位置，并继续寻找下一个匹配位置。最后返回找到的最长子串的开始位置即可。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * KMP算法中的计算next数组的函数
     */
    void computeNextArray(const string& pattern, vector<int>& next) {
        int m = pattern.length();
        int j = 0; // 模式串的指针

        for (int i = 1; i < m; ++i) {
            while (j > 0 && pattern[i] != pattern[j]) {
                j = next[j - 1];
            }

            if (pattern[i] == pattern[j]) {
                ++j;
            }

            next[i] = j;
        }
    }

    int findLongestSubstring(string s, vector<string>& words) {
        // 将所有的单词拼接成一个模式串
        string pattern = "";
        for (const string& word : words) {
            pattern += word;
        }

        int n = s.length();
        int m = pattern.length();

        // 计算模式串的next数组
        vector<int> next(m, 0);
        computeNextArray(pattern, next);

        int i = 0; // 主串的指针
        int j = 0; // 模式串的指针
        int start = -1;
        int maxLength = -1;

        while (i < n) {
            if (s[i] == pattern[j]) {
                ++i;
                ++j;
            } else {
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    ++i;
                }
            }

            if (j == m) {
                // 找到了一个匹配的子串
                if (i - j > maxLength) {
                    maxLength = i - j;
                    start = i - m;
                }
                // 继续寻找下一个匹配位置
                j = next[j - 1];
            }
        }

        return start;
    }
};