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

1
class Solution {
2
public:
3
    int strStr(string haystack, string needle) {
4
        if (needle.empty()) return 0;
5
        int n = haystack.size(), m = needle.size();
6

7
        // 只需要遍历到能够容纳 needle 的最后位置
8
        for (int i = 0; i <= n - m; ++i) {
9
            int j = 0;
10
            while (j < m && haystack[i + j] == needle[j]) {
11
                j++;
12
            }
13
            if (j == m) return i; // 全部匹配成功
14
        }
15
        return -1;
16
    }
17
};

1
#include <vector>
2
#include <string>
3
using namespace std;
4

5
class Solution {
6
public:
7
    int strStr(string haystack, string needle) {
8
        if (needle.empty()) return 0;
9
        int n = haystack.size(), m = needle.size();
10
        vector<int> next = buildNext(needle);
11

12
        for (int i = 0, j = 0; i < n; ) {
13
            if (haystack[i] == needle[j]) {
14
                i++; j++;
15
                if (j == m) return i - j; // 完全匹配成功
16
            } else {
17
                if (j > 0) j = next[j - 1]; // 利用 next 数组“跳跃”
18
                else i++; // 模式串已到头，文本串后移
19
            }
20
        }
21
        return -1;
22
    }
23

24
private:
25
    // 构建 Next 数组（最长公共前后缀）
26
    vector<int> buildNext(const string& p) {
27
        int m = p.size();
28
        vector<int> next(m, 0);
29
        for (int i = 1, len = 0; i < m; ) {
30
            if (p[i] == p[len]) {
31
                next[i++] = ++len;
32
            } else if (len > 0) {
33
                len = next[len - 1]; // 回退 len
34
            } else {
35
                next[i++] = 0;
36
            }
37
        }
38
        return next;
39
    }
40
};