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

原始题目:
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

第一次学习KMP算法，参考的是改进版的动态规划算法。
https://zhuanlan.zhihu.com/p/83334559
其本质为一个有限状态机，通过needle构造出一个状态机，状态个数为needle的长度，然后不断输入heystack中的字符，处理状态机的改变。

状态机构造时的核心思路为：当无法继续向下匹配时，向影子状态，即代码中的X，即当前最长前缀所在的位置（X始终比当前遍历到的位置慢一步）询问下一个应该到达的状态。
本算法为了便于理解，在每个位置状态，多用了255个空间，但总的空间复杂度依旧保持不变。

```c++
class Solution {
public:
    int strStr(string haystack, string needle) {
        //字符串匹配？似乎有什么kmp算法？暴力匹配的话，最大复杂度为O(mn)
        //直接使用kmp，首先构建next数组，本文选择二维的数组
        //从haystack中查找needle
        vector<vector<int>> dp(needle.length(), vector<int>(255, 0)); //char a的取值范围就是0-255
        //初始状态为0
        int X = 0; //标记上一个状态
        dp[0][needle[0]] = 1; //只有这种情况下，才转移到1，其余情况都保留在0
        for (int i = 1; i < needle.size(); i++) {
            for (int c = 0; c < 255; c++) {
                if (c == needle[i]) {
                    dp[i][c] = i + 1; //可以到达下一个i
                } else {
                    //构造状态机，回到影子状态的位置，并前往下一个位置
                    dp[i][c] = dp[X][c];
                }
            }
            //更新影子状态
            X = dp[X][needle[i]]; //这个位置始终比当前位置慢一个位次，其实他的含义就是匹配needle[0,i-1]也就是前缀的最后位置。然后从这个位置向后匹配。
        }
        //开始匹配haystack
        int cur = 0;
        for (int i = 0; i < haystack.length(); i++) {
            cur = dp[cur][haystack[i]];
            //检查是否匹配到了最后一个元素
            if (cur == needle.length()) {
                return i - needle.length() + 1;
            }
        }
        return -1;
    }
};
```

Alangy's Blog

导航

近期文章

友情链接