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

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

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

• 解法一： 首先暴力匹配尝试下

class Solution {
public:
    int strStr(string haystack, string needle)
    {
        for (int i = 0; i < haystack.size(); i++) {
            bool flag = 1;

            for (int j = 0; j < needle.size(); j++) {
                if (i+j>=haystack.size() || haystack[i + j] != needle[j])
                {
                    flag = 0;
                    break;
                }
            }

            if (flag)
                return i;
        }

        return -1;
    }
};

• 解法2：KMP

class Solution {
public:
    vector<int> prefix;

public:
    //前缀函数
    void prefix_func(const string& s) {
        int n = (int)s.length();
        prefix.resize(n);
        for (int i = 1; i < n; i++) {
            int j = prefix[i - 1];
            while (j > 0 && s[i] != s[j]) j = prefix[j - 1];
            if (s[i] == s[j]) j++;
            prefix[i] = j;
        }

    }

    int strStr(string haystack, string needle) {
        string cur = needle + "#" + haystack;
        int sz1 = haystack.size();
        int sz2 = needle.size();

        vector<int>v;
        prefix_func(cur);
        for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
            if (prefix[i] == sz2) return i - 2 * sz2;
        }

        return -1;
    }

};