算法 - 字符串匹配 - Rabin-Karp算法

本文主要是介绍算法 - 字符串匹配 - Rabin-Karp算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Rabin-Karp算法

介绍

Rabin-Karp字符串匹配算法与朴素字符串匹配算法类似，都要比较每一个字符串，不同的是Rabin-Karp算法对字符串做预处理，将字符转换为进制数并取模。预处理时间O(m), 匹配时间是O((n - m + 1) m)，m是匹配字符串长度，n是目标字符串长度。

RaBin-Karp算法：

1. 假设待匹配字符串的长度为M，目标字符串的长度为N（N>=M）；
2. 首先计算待匹配字符串的hash值，计算目标字符串前M个字符的hash值；
3. 比较前面计算的两个hash值，比较次数N-M+1：

1.若hash值不相等，则继续计算目标字符串的下一个长度为M的字符子串的hash值

2.若hash值相同，则需要使用朴素算法再次判断是否为相同的字串；

伪代码：

RABIN_KARP_MATCHER(T, P, d, q)    //  输入 文本T，模式P，使用进制d，素数qn = T.lengthm = P.lengthh = d^(m - 1) mod qp = 0t = 0for i = 1 to m                // preprocessingp = (d * p + P[i]) mod qt = (d * t + T[i]) mod qfor s = 0 to n - m            //matchingif p == tif P[1..m] == T[s+1..s+m]print "Pattern occurs with shift " sif s < n - mt = (d * (t - T[s + 1] * h) + T[s + m + 1]) mod q

 源码（参考https://blog.csdn.net/chenhanzhun/article/details/39895077）：

// Rabin Karp Algorithm #include<iostream>
#include<string>using namespace std;void Rabin_Karp_search(const string &T, const string &P, int d, int q)
{int m = P.length();int n = T.length();int i, j;int p = 0;  // hash value for patternint t = 0; // hash value for txtint h = 1;// The value of h would be "pow(d, M-1)%q"for (i = 0; i < m-1; i++)h = (h*d)%q;// Calculate the hash value of pattern and first window of textfor (i = 0; i < m; i++){p = (d*p + P[i])%q;t = (d*t + T[i])%q;}// Slide the pattern over text one by one for (i = 0; i <= n - m; i++){// Chaeck the hash values of current window of text and pattern// If the hash values match then only check for characters on by oneif ( p == t ){/* Check for characters one by one */for (j = 0; j < m; j++)if (T[i+j] != P[j])break;if (j == m)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]cout<<"Pattern found at index :"<< i<<endl;}// Calulate hash value for next window of text: Remove leading digit, // add trailing digit           if ( i < n-m ){t = (d*(t - T[i]*h) + T[i+m])%q;// We might get negative value of t, converting it to positiveif(t < 0) t = (t + q); }}
}int main()
{string T = "Rabin–Karp string search algorithm: Rabin-Karp";string P = "Rabin";int q = 101;  // A prime numberint d = 16;Rabin_Karp_search(T, P,d,q);system("pause");return 0;
}

参考资料：

《算法导论》第三版

这篇关于算法 - 字符串匹配 - Rabin-Karp算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---