本文主要是介绍C++ 字符串匹配(KMP算法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
KMP算法思想:
字符串匹配算法要求输入主串(string)和子串(pattarn),然后返回子串在主串中第一次出现的位置。 KMP的思想减少字符串比对次数,从以下两方面入手:
(1):一是检查字串中是否有前后相同的字符,并记录在一个数组中。如果有前后相同的字符,则加以标记,在比较时可以跳过,因为前面已比较过了,后面不用重复比较一遍。
(2):二是采用主串不回退的原则,主串一直向前遍历,这样就会显著减少匹配次数。
#include <iostream>using namespace std; #include <queue>std::vector<int> build_next(const char* substr, int len)
{std::vector<int> next{};next.push_back(0);int prefix = 0;int i = 1; while (i < len){if (substr[prefix] == substr[i]){prefix += 1;next.push_back(prefix);i += 1;}else{if (prefix == 0){next.push_back(0);i += 1;}else{prefix = next[prefix - 1];}}}return next;
}int strmatch_kmp(const char* str, const char* substr, int index)
{int len1 = strlen(str);int len2 = strlen(substr);std::vector<int> next = build_next(substr, len2);int i = 0;int j = 0; while (i < len1 && j < len2){if (str[i] == substr[j]){i++;j++;}else if (j > 0){j = next[j-1]; //匹配失败,字串回退到前面next[j-1]的位置}else{i++; //第一次就匹配失败了,主串后移}}if (j = len2){return i - j;}else{return -1;}
}int main()
{const char* str = "goodgoogle";const char* sub = "google";//const char* str = "abcdefgabcedfsdfe";//const char* sub = "abcdefx";std::cout << (str + strmatch_kmp(str, sub, 0)) << std::endl;return 0;
}
这篇关于C++ 字符串匹配(KMP算法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!