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

Posted on | In |
Words count in article: 257 | Reading time ≈ 1

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

示例：

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

分析：

1
KMP算法

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int strStr(string s, string p) {
        int m = s.size(), n = p.size();
        s = " " + s, p = " " + p;
        vector<int> ne(n + 1);
        int res = -1;
		// 求解next数组
        for (int i = 2, j = 0;i <= n;i ++) {
            while (j && p[i] != p[j + 1]) j = ne[j];
            if (p[i] == p[j + 1]) j ++;
            ne[i] = j;
        }
		// 匹配过程
        for (int i = 1, j = 0;i <= m;i ++) {
            while (j && s[i] != p[j + 1]) j = ne[j];
            if (s[i] == p[j + 1]) j ++;
            if (j == n) {
                res = i - n;
                j = ne[j];
                break;
            }
        }

        return res;
    }
};

[原题链接](28. 找出字符串中第一个匹配项的下标 - 力扣（Leetcode）)

0%