🎈 作者Linux猿

🎈 简介CSDN博客专家🏆华为云享专家🏆Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我关注我有问题私聊

🎈 关注专栏 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

---

目录

一、题目描述

1.1 输入描述

1.2 输出描述

1.3 测试样例

1.3.1 示例 1

二、解题思路

三、代码实现

四、时间复杂度

---

一、题目描述

给你两个字符串 t 和 p要求从 t 中找到一个和 p 相同的连续子串并输出该子串的第一个字符的下标。

1.1 输入描述

输入包括两行分别表示 t 和 p保证t的长度不小于 p而且t的长度不超过 1000000 p 的长度不超过 10000。

1.2 输出描述

如果能从 t 中找到一个和 p 相等的连续子串则输出该子串第一个字符在 t 中的下标下标以 1 开始

如果不能则输出 “NO”如果包含多个这样的子串则输出第一个字符下标最小的那个。

1.3 测试样例

1.3.1 示例 1

输入

AVERDXIVYERDIAN
RDXI

输出

4

二、解题思路

本题主要考查 KMP 算法直接使用 KMP 即可注意结果的输出不包含时输出 NO。

三、代码实现

代码实现如下所示。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int MS = 1000000 + 5;
int nextArr[MS];
void getNext(const string &p)
{
    nextArr[0] = 0;
    int n = p.length();
    for (int i = 1, j = 0; i < n; ++i) {
        while (j && p[i] != p[j])
            j = nextArr[j - 1];
        if (p[i] == p[j]){
            j++;
            nextArr[i] = j;
        }
    }
}
int kmp(const string &s, const string &p)
{
    int n = s.length();
    int m = p.length();
    for (int i = 0, j = 0; i < n; ++i) {
        while (j && s[i] != p[j])
            j = nextArr[j - 1];
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            return i - j + 1;
        }
    }
    return -1; // 匹配失败
}

int main()
{
    string s;
    string p;
    while (getline(cin, s)) {
        getline(cin, p);
        getNext(p);
        int ans = kmp(s, p);
        if (ans == -1) {
            cout<< "NO" <<endl;
        } else {
            cout<< ans + 1 <<endl;
        }
    }

    return 0;
}

四、时间复杂度

时间复杂度O(n + m)。

本题「时间复杂度」等于 KMP 算法的时间复杂度假设原字符串的长度为 n待查找的字符串的长度为 mKMP 算法计算 next 数组的时间复杂度约为 [ m, 2 * m ]计算最终结果的时间复杂度为 [ n, 2 * n ]所以总的「时间复杂度」为 O (n + m)。 

---

🎈 感觉有帮助记得「一键三连」支持下哦有问题可在评论区留言💬感谢大家的一路支持🤞猿哥将持续输出「优质文章」回馈大家🤞🌹🌹🌹🌹🌹🌹🤞

---