朴素字符串匹配算法
这里假设text是一个文本，长度为n。pattern是需要匹配的子串，长度为m。
朴素字符串匹配算法，通过简单的循环，从头对比text中，每个长度为m的子串是否与pattern相等：
NaiveStringMatch.png
朴素字符串匹配算法实现十分简单，因为没有做任何预处理，时间复杂度为0((n-m+1)*m)：
/*
* @brief 朴素字符串匹配
* @return 返回pattern在text匹配成功的索引值，若未匹配成功，返回空数组
*/
vector<int> NaiveStringMatch(string text,string pattern) {
vector<int> matched_index;
int t_len = text.size();
int p_len = pattern.size();
if (t_len < p_len) {
return matched_index;
}
for (int i = 0; i < t_len - p_len + 1; i++) {
for (int j = 0; j < p_len; j++) {
if (text[i + j] != pattern[j]) {
break;
}
if (j == p_len - 1) {
matched_index.push_back(i);
}
}
}
return matched_index;
}
Rabin-Karp 算法
为了方便理解， 在这里先假设，T为长度n的文本，P为长度m的模式，T、P只包含0-9的数字字符。因此，可以简单的将P字面的值，作为P的值。
例如： P= "123" , 这时候P的值就是123。
设p为P[1 : m]的值，Ts 为T[s : s + m - 1]的值，当p == Ts 时，可知字符串匹配成功。
相比朴素字符串匹配算法，如果，能够通过Ts的值，直接计算出Ts+1的值，就可以跳过子串对比的过程。
假设 T = ”123456“ ， m = 3。 则有T0 = 123，T1 = 234。 T1相对于T0去除了一个高位1，增加了一个低位4
由上可推出 Ts+1 =10 * (Ts - T[s] * 10^(m-1)) + T[s+1]
现在的问题是，当m太大，上面对于Ts+1的计算，就不可能在常数时间内完成。
这里就需要,找到一个合适的q,运用模运算,得到：
Ts+1 = (10 * (Ts - T[s] * h) + T[s+1] ) mod q
h = 10^(m - 1) mod q
运用模运算,可能会出现，T[s : s + m - 1] ！= P[1 : m]，但是Ts == p 的情况。因此当Ts == p时，需要再次判断T[s : s + m - 1] 和 P[1 : m] 是否相等。
如下图，P = ”31415“，q为质数13，通过计算p = 7：
Rabin-Karp.png
为推广到任意字符匹配，我们可以将底10换成其他数值
Ts+1 = (d * (Ts - T[s] * h) + T[s+1] ) mod q
h = d^(m - 1) mod q
例如：ASCII字符最大值为128，我们使 d = 128，可以进行ASCII字符的匹配。
c++代码实现如下：
/*
* @brief Rabin-Karp 匹配算法
* @return 返回pattern在text匹配成功的索引值，若未匹配成功，返回空数组
*/
vector<int> RabinKarpMatch(string text, string pattern) {
vector<int> matched_index;
int t_len = text.size();
int p_len = pattern.size();
/* 以128为底，匹配所有ASCII码字符 质数选择： 113 */
int d = 128;
int q = 113;
int h = pow(d, p_len - 1);
h = fmod(h,113);
int t_hash = 0;
int p_hash = 0;
for (int i = 0; i < p_len; i++) {
p_hash = fmod((d * p_hash + pattern[i]) , q);
t_hash = fmod((d * t_hash + pattern[i]), q);
}
cout << "p_hash: "<< p_hash << endl;
for (int i = 0; i < t_len - p_len + 1; i++) {
cout <<i<<".t_hash:" << t_hash << endl;
if (t_hash == p_hash) {
for (int j = 0; j < p_len; j++) {
if (text[i + j] != pattern[j]) {
break;
}
if (j == p_len - 1) {
matched_index.push_back(i);
}
}
}
if (i < t_len - p_len) {
t_hash = fmod((d * (t_hash - text[i] * h) + text[i + p_len]) , q);
while (t_hash < 0) {
t_hash += q;
}
}
}
return matched_index;
}
KMP算法
这里引入一些概念：
字符串的前缀：符号串左部的任意子串（或者说是字符串的任意首部）
字符串的后缀：符号串右部的任意子串（或者说是字符串的任意尾部）
kmp.png
c++代码实现：
static vector<int> KmpPrefixComputing(string pattern) {
vector<int> prefix(pattern.size(), 0);
/* pattern中已匹配字符数 */
int k = 0;
prefix[0] = k;
/* 本质是由pattern[0:] 取匹配 pattern[1:] 求pattern[0:i]后缀的关于pattern的最长前缀 */
for (int i = 1; i < pattern.size(); i++) {
while (k > 0 && pattern[k] != pattern[i]) {
k = prefix[k - 1];
}
if (pattern[k] == pattern[i]) {
k++;
}
prefix[i] = k;
}
return prefix;
}
/*
* @brief KMP 匹配算法
* @return 返回pattern在text匹配成功的索引值，若未匹配成功，返回空数组
*/
vector<int> KmpMatch(string text, string pattern) {
vector<int> matched_index;
vector<int> prefix = KmpPrefixComputing(pattern);
int k = 0;
for (int i = 0; i < text.size(); i++) {
while (k > 0 && pattern[k] != text[i]) {
k = prefix[k - 1];
}
if (pattern[k] == text[i]) {
k++;
}
if (k == pattern.size()) {
matched_index.push_back(i - pattern.size() + 1);
k = prefix[k];
}
}
return matched_index;
}
