没错，终于到了大名鼎鼎的kmp了，久仰大名而不知其为何物的东西，终于要好好学习了！！！
题目描述：
给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。暴力
依旧先搞清楚暴力怎么做
string s, p; // s:长串 p:短串
int n = s.size();
int m = p.size();
for (int i = 0; i < s.size(); i ++ ) // 假设从 i 开始匹配能成功
{
bool flg = 1; // 成功状态
int j = 0;
for (j = 0; j < p.size(); j ++ )
{
if (s[i + j] != p[j])
{
flg = 0;
break;
}
}
if (flg) cout << i << ' ';
}很明显的暴力匹配，不多解释了，时间复杂度O(n*m)
优化
非常难懂，暂且先记一下笔记，防止自己忘了。
首先是因为一大堆刚刚听懂的模模糊糊的暂时我还没法讲出来的理由，要求模板字符串p的最长公共前后缀，此时需要数组next[i] = j 来表示字符串p中第1个到第j个和第i – j + 1个到第i个完全一致，更为详细地说，表示的是s[i – j – 1]到s[i – 1]和p[1]到p[j]（此处为1-base）完全一致，但s[i]和s[j + 1]不同
好吧放弃解释，经由Autleave老师推荐的讲解视频懂了，直接贴视频
最后贴一下代码
#include <bits/stdc++.h>
using namespace std;
vector<int> kmp_search(string s, string p)
{
vector<int> ans;
string str = p + '#' + s; // #为既不出现在s中也不出现在p中的字符
vector<int> pi(str.size());
for (int i = 1; i < str.size(); i ++ )
{
int len = pi[i - 1];
while (len != 0 && str[i] != str[len])
len = pi[len - 1];
if (str[i] == str[len])
pi[i] = len + 1;
if (pi[i] == p.size())
ans.push_back(i - p.size() * 2);
}
return ans;
}
int main()
{
int n, m;
string s, p;
cin >> n >> p >> m >> s;
auto ans = kmp_search(s, p);
for (auto i : ans) cout << i << ' ';
return 0;
}
评论（0）
暂无评论