首页 > 代码库 > 基本算法——字符串查找之KMP算法
基本算法——字符串查找之KMP算法
虽然，c++标准库中为我们提供了字符串查找函数，但我们仍需了解一种较为快捷的字符串匹配查找——KMP算法。
在时间复杂度上，KMP算法是一种较为快捷的字符串匹配方法。
实现代码如下:
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <stdexcept> 5 using namespace std; 6 7 void get(const string &s, vector<int> &next) 8 { 9 int i = 0, j = -1;10 next.push_back(-1);11 12 while(i < s.size() - 1)13 {14 if(j == -1 || s[i] == s[j])15 {16 ++ i;17 ++ j;18 if(s[i] != s[j])19 next.push_back(j);20 else21 next.push_back(next[j]);22 }23 else24 j = next[j];25 }26 }27 28 int kmp(const string &s, const string &d)29 {30 vector<int> next;31 get(d, next);32 33 int i = 0, j = 0;34 while(i < s.size() && j < d.size())35 {36 if(j == -1 || s[i] == d[j])37 {38 ++ i;39 ++ j;40 }41 else42 j = next[j];43 }44 45 if(j >= d.size())46 return i - d.size();47 else48 return -1;49 }50 51 int main(int argc, const char *argv[])52 {53 string s("ababcabcacbab");54 string d("abcac");55 56 int i = kmp(s, d);57 if(i == -1)58 cout << "false" << endl;59 else60 cout << i << endl;61 return 0;62 }
在实现该算法中，我们额外提供一个vector数组，来保存相对的字符顺序，以避免我们重复判断该处的字符是否相等。
具体原理部分详见《数据结构》或《算法导论》。
基本算法——字符串查找之KMP算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。