本文主要是介绍kmp 算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<string>
#include<iostream>
using namespace std;
vector<int> getnext(string s) {
vector<int> next(s.size(),0);
next[0] = 0;
int j = 0;
for (int i = 1; i < s.size();i++) {
if (j > 0 && s[i] != s[j]) {
j = next[j - 1]; //类似于动态规划,当前未知不相等,就回退到j-1 的位置,这个位置计算好了
}
if (s[i] == s[j]) {
j++;
next[i] = j;
}
}
for (auto &k : next) {
cout << k;
}
cout << endl;
return next;
}
int kmp(string S, string T) {
int res = 0;
int i = 0;
int j = 0;
vector<int> next = getnext(S);
for (int i = 0; i < T.size(); i++) {
if (j > 0 && T[i] != S[j]) {
j = next[j - 1];
}
if (T[i] == S[j]) {
j++;
}
if (j == S.size()) {
res++;
}
}
cout << res << endl;
return res;
}
int main() {
string s = "aabaaab";
string t = "abaaabaaabcd";
kmp(s,t);
}
这篇关于kmp 算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!