Loading... > 本文是之前在其他博客上撰写的,现全部转移过来。 偶然发现了hihoCoder上提供了一个“hiho一下”的编程练习,感觉相对系统且比较基础,适合我这种啥都不会的-_-||| 发现的比较晚,已经到了第三周的题目。第三周是学习KMP算法。这是一个非常经典的字符串匹配算法。所谓字符串匹配,就是判断一串字符(原串)中是否存在一个特定的字符串(模式串)。最开始,参考了下述两篇文章,编写了算法。 > [字符串匹配的KMP算法][1] > > [从头到尾彻底理解KMP(2014年7月版)][2] 具体原理就先不写了,有时间再撸吧。 这是我的第一版程序 ```cpp #include <string> #include "iostream" using namespace std; int theNumofPattern = 0; void nextCal(string s, int next[]); int kmpCal(string s, string t); int main( ) { int theNumofTest = 0; string s; string t; cin >> theNumofTest; while (theNumofTest--) { cin >> t; cin >> s; int sLength = s.length(); int tLength = t.length(); int theLocation = 0; while (theLocation < sLength) { if (theLocation != 0) { s = s.substr(theLocation - tLength + 1, sLength); } theLocation = kmpCal(s, t); if (theLocation == s.length()) break; } cout << theNumofPattern << endl; theNumofPattern = 0; } return 0; } int kmpCal(string s, string t) { int sLength = s.length(); int tLength = t.length(); int next[10001]; nextCal(t, next); int i = 0; int j = 0; while ((i < sLength) && (j < tLength)) { if (s[i] != t[j]) { i = i - next[j]; j = 0; } else { i++; j++; } } if (j == tLength) { // printf("%d\n", i-1); theNumofPattern++; } else { // printf("%s\n", "none"); } return i; } void nextCal(string s, int next[]) { int len = s.length(); next[0] = 0; for (int i = 1; i < len; i++) { int k = next[i - 1]; while (s[i] != s[k] && k != 0) k = next[k - 1]; if (s[i] == s[k]) next[i] = k + 1; else next[i] = 0; } for (int i = 0; i < len; i++) { next[len - 1 - i] = next[len - 2 - i]; } next[0] = -1; } ``` 在电脑上测试样例通过,于是马上提交代码,结果却Time Limit Exceeded。 看来自己编写的确实算法复杂度太差了。回头看了看,循环太多,但是却又无从下手修改。 后来经大神[xmfbit][3]指点,参考下面这篇博客重新编写了程序。 [KMP算法详解][4] 第二版程序如下: ```cpp #include <string> #include "iostream" using namespace std; int theNumofPattern = 0; void nextCal(string s, int *next); void kmpCal(string s, string t, int next[]); int main( ) { int theNumofTest = 0; string s; string t; int next[10001]; cin >> theNumofTest; while (theNumofTest--) { cin >> t; cin >> s; nextCal(t, next); kmpCal(s, t, next); } return 0; } void nextCal(string s, int *next) { next[0] = 0; int j = 0; int sLength = s.length(); for (int i = 1; i < sLength; i++) { while ((j > 0) && (s[j] != s[i])) j = next[j - 1]; if (s[j] == s[i]) { j = j + 1; } next[i] = j; } } void kmpCal(string s, string t, int next[]) { int i = 0; int j = 0; int sLength = s.length(); int tLength = t.length(); for (i = 0; i < sLength; i++) { while ((j > 0) && (t[j] != s[i])) j = next[j - 1]; if (t[j] == s[i]) j = j + 1; if (j == tLength) { theNumofPattern++; //cout << i - tLength << endl; j = next[j - 1]; } } cout << theNumofPattern << endl; theNumofPattern = 0; } ``` 程序简短了许多,测试成功后,提交代码。 AC了~ 耗时241ms,果然要比自己瞎编的要强得多啊。 [1]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html [2]: http://blog.csdn.net/v_july_v/article/details/7041827 [3]: http://xmfbit.github.io/ [4]: http://www.matrix67.com/blog/archives/115 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏