字符串-KMP-1—算法—6.12

28. 找出字符串中第一个匹配项的下标 – 力扣（LeetCode）

给你两个字符串 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 仅由小写英文字符组成

其他解法

https://www.yuque.com/wumingyinfu/sjzu_jsj/ghizwvfwarnzs373

题解：innno：

/**
 * ClassName: ${NAME}
 * package: ${PACKAGE_NAME}
 * Description:
 * @Author: innno
 * @Create: 2024/2/27 - 21:54
 * @Version: v1.0
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;


ll recognize(auto &&s1, auto &&s2);

void makenext(auto &&next, auto &&s2);

int main()
    {
        ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
        string s1, s2;//s1为待查字符串，s2为模板字符串
        cin >> s1 >> s2;
        cout << recognize(s1, s2);
        return 0;
    }

void makenext(auto &&next, auto &&s2)
    {
        ll j = 0;

        next[0] = 0;
        for (ll i = 1; i < s2.size(); i++)
            {
                while (j > 0 && s2[i] != s2[j])//while循环的目的是不断找到合适的j
                    {
                        j = next[j - 1];//精妙，KMP的执行精髓，背下来即可
                    }
                if (s2[j] == s2[i])//找到合适的j
                    {
                        j++;
                    }
                next[i] = j;
            }
    }

ll recognize(auto &&s1, auto &&s2)
    {
        vector<ll> next(s2.size());
        makenext(next, s2);
        ll j = 0;
        for (ll i = 1; i < s1.size(); i++)//可以观察到，此结构与next数组的形成有异曲同工之妙
            {
                while (j > 0 && s1[i] != s2[j])//同上，可以观察到，s1数组，即待查字符串，与next算法中的s【i】为同一结构，而s2数组，即模板字符串，与next算法中的s【j】同一结构
                    {
                        j = next[j - 1];//同上
                    }
                if (s1[i] == s2[j])//找到合适的j
                    {
                        j++;
                    }
                if (j == s2.size())//已找到合适的，即中断
                    {
                        return (i - s2.size() + 1);//返回的是下标位置（前下标）
                    }
            }
    }