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

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

在我的回答中使用了kmp算法，可以极大的节省所用时间

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0; // needle 为空，返回0

        // 构建部分匹配表
        vector<int> lps = computeLPS(needle);

        int i = 0, j = 0;
        while (i < haystack.size()) {
            if (haystack[i] == needle[j]) {
                ++i;
                ++j;
            }
            if (j == needle.size()) {
                return i - j; // 找到了完整匹配，返回起始位置
            } else if (i < haystack.size() && haystack[i] != needle[j]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    ++i;
                }
            }
        }
        
        return -1; // 没有找到匹配
    }

private:
    vector<int> computeLPS(string needle) {
        int n = needle.size();
        vector<int> lps(n, 0);
        int len = 0; // 当前匹配的前缀的长度
        int i = 1;
        
        while (i < n) {
            if (needle[i] == needle[len]) {
                ++len;
                lps[i] = len;
                ++i;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    ++i;
                }
            }
        }
        
        return lps;
    }
};

• strStr 方法：

  • 先处理特殊情况，如果 needle 为空，则直接返回 0。
  • 调用 computeLPS 方法计算 needle 的部分匹配表。
  • 使用双指针 i 和 j 在 haystack 上进行匹配：
    • 如果当前字符匹配，则同时向后移动 i 和 j。
    • 如果 j 移动到 needle 的末尾，返回匹配起始位置 i - j。
    • 如果当前字符不匹配，并且 j 不为 0，则根据部分匹配表调整 j。
    • 如果 j 为 0，则移动 i 继续尝试匹配。
  • 如果循环结束仍未找到匹配，则返回 -1。

• computeLPS 方法：

  • 构建 needle 的部分匹配表 lps。
  • 使用 len 记录当前匹配的前缀的长度，i 表示当前字符。
  • 根据当前字符与前缀的匹配情况更新 len 和 lps[i]。
  • 如果不匹配，根据 len 调整 len 的值。

总结

通过使用 KMP 算法，可以高效地在 haystack 中查找 needle 的第一个匹配项的位置，时间复杂度为 O(m + n)，其中 m 是 haystack 的长度，n 是 needle 的长度。这种方法利用部分匹配表，在匹配过程中避免了回溯，使得算法效率得到了显著提升。

但是对于不熟悉kmp算法的人下面的一种方法更加简单

#include <string>

using namespace std;

class Solution {
public:
    int strStr(string haystack, string needle) {
        int hLen = haystack.length(); // 获取 haystack 的长度
        int nLen = needle.length();   // 获取 needle 的长度
        
        // 遍历 haystack，确保剩余长度足够容纳整个 needle
        for (int i = 0; i <= hLen - nLen; ++i) {
            int j = 0;
            // 逐个字符比较 needle 和 haystack 中的对应位置
            for (j = 0; j < nLen; ++j) {
                if (needle[j] != haystack[i + j]) // 不匹配时退出内循环
                    break;
            }
            
            if (j == nLen) // 如果 j 等于 needle 的长度，说明找到匹配
                return i; // 返回匹配起始位置
        }
        
        return -1; // 遍历完整个 haystack 后仍未找到匹配，返回 -1
    }
};

方法较为简单，但运行时间较长