本文最后更新于:2022年11月22日 下午
本文比对了 KMP 以及 C++ string
的find
方法在检查 a 是否为 b 子串这一问题上的效率。
尽管字符串长度已经达到了 104 这一量级,但是在 test case 数量为 105 时,KMP 表现仍没有find
好.
首先,毫无疑问,从时间复杂度上分析,KMP 确实胜于 find
的暴力匹配,但是 KMP 会在 build next table 上花费比较多的时间,在字符串长度仍不够大时,并无法体现它的优势。
同时在我的测试情景中,next 表 Build 完毕后只会在一个测试用例中使用,无疑是浪费了。
而find
方法只所以实现上采用暴力匹配,也是因为其使用于更 common 的场景,而 KMP 也需要分配额外的内存来进行 next 表的构建
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
| #include <iostream> #include <string> #include <regex> #include <ctime> #include <unistd.h> #include <chrono> #define CASESNUM 100000 using namespace std; bool checkSubstring(string a, string b); vector<pair<string, string>> generateCases(int len);
class Solution{ public: vector<int> next; string p; int m; Solution(string pattern){ p = pattern; m = p.size(); p.insert(p.begin(),' '); next.reserve(m + 1); for(int i = 2, j = 0; i <= m; i++){ while(j and p[i] != p[j + 1]) j = next[j]; if(p[i] == p[j + 1]) j++; next[i] = j; } }
bool kmpCheckSubstring(string s){ int n = s.size(); if(m == 0){ return true; } s.insert(s.begin(),' '); for(int i = 1, j = 0; i <= n; i++){ while(j and s[i] != p[j + 1]) j = next[j]; if(s[i] == p[j + 1]) j++; if(j == m) return true; } return false; } };
template <class TimeT = std::chrono::milliseconds, class ClockT = std::chrono::steady_clock> class Timer{ using timep_t = typename ClockT::time_point; timep_t _start = ClockT::now(), _end = {};
public: void tick() { _end = timep_t{}; _start = ClockT::now(); }
void tock() { _end = ClockT::now(); }
template <class TT = TimeT> TT duration() const { return std::chrono::duration_cast<TT>(_end - _start); } }; int main(void){ string a, b; srand( (unsigned) time(NULL) * getpid()); Timer clock1, clock2;
vector<pair<string, string>> cases = generateCases(CASESNUM); clock1.tick(); for(int i = 0; i < CASESNUM; i++){ checkSubstring(cases[i].first, cases[i].second); } clock1.tock(); cout << "Run time = " << clock1.duration().count() << " ms\n"; clock2.tick(); Solution solution(cases[0].second); for(int i = 0; i < CASESNUM; i++){ solution.kmpCheckSubstring(cases[i].first); } clock2.tock(); cout << "Run time = " << clock2.duration().count() << " ms\n"; } std::string gen_random(const int len) { std::string tmp_s; static const char alphanum[] = "0123456789" "ABCDEFGHIJKLMNOPQRSTUVWXYZ" "abcdefghijklmnopqrstuvwxyz"; tmp_s.reserve(len); for (int i = 0; i < len; ++i) tmp_s += alphanum[rand() % (sizeof(alphanum) - 1)]; return tmp_s;
}
vector<pair<string, string>> generateCases(int len){ vector<pair<string, string>> cases; cases.reserve(len); int substringLen = rand() % 20000 + 10000; string substring = gen_random(substringLen); while(len--){ int choose = rand() % 2; if(choose){ int prefixLen = rand() % 10000 + 80000; int suffixLen = rand() % 10000 + 80000; string prefixString = gen_random(prefixLen), suffixString = gen_random(suffixLen); cases.emplace_back(prefixString + substring + suffixString, substring); }else{ int anotherStringLen = rand() % 20000 + 10000; cases.emplace_back(substring, gen_random(anotherStringLen)); } } return cases; }
bool checkSubstring(string b, string a){ return b.find(a) != b.npos; }
|