字符串处理 Rabin-Karp (Rolling Hash)及
关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
LeetCode题目：686 Repeated String Match
Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.
For example, with A = "abcd" and B = "cdabcdab".
Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").
传统算法代码如下：时间复杂度O(length(A) * length(B))
class Solution {
public int repeatedStringMatch(String A, String B) {
for(int i = 0; i < A.length(); i++) {
// find the first match index
if(A.charAt(i) == B.charAt(0)) {
int times = 1;
int k = i;
int j = 0;
while(j < B.length() && A.charAt(k) == B.charAt(j)) {
j++;
// reach the end of A and not reach the end of B, times + 1
if(k == A.length() - 1 && j < B.length()) {
k = 0;
times++;
}
else {
k++;
}
}
// reach the end of B
if(j == B.length()) {
return times;
}
}
}
return -1;
}
}
Rabin-Karp (Rolling Hash 旋转哈希)算法
字符串可以理解为字符数组，而字符可以被转换为整数，可以把字符串当成一个整形数组。
找到一种方式将一组整形数字转化为一个数字，就能够使得我们借助一个预期的输入值来Hash字符串。
假设，一个模式串 P(需要被匹配的串)长度为L，需要在其中查找匹配的串S长度为N。
一种在S中查找P的方式为：
- 哈希
P得到h(P)，时间复杂度O(L) - 从
S的索引为0开始来枚举S里长度为L的子串，哈希子串并计算出h(P)'，时间复杂度O(N*L)。 - 如果一个子串的哈希值
h(P)'与h(P)匹配，将该子串与P进行比较，时间复杂度O(L)
这个做法的时间复杂度为 O(N*L)。我们可以通过使用 Rolling Hash 来优化这种做法。在上述步骤2中，我们看到对于 O(N) 的子串，都花费了 O(L) 来哈希他们，然而可以看到这些子串中很多字符都是重复的。
我们可以利用前一个子串的计算结果哈希值来计算当前子串的哈希值。因此在上述步骤2中，时间复杂度可以优化为O(N)
假设第一个子串哈希值H0 = (S[0] * 10^2 + S[1] * 10^1 + S[2] * 10^0) mod m
则第二个子串哈希值H1 = (10 * H0 - S[0] * 10^3 + S[3] * 10^0) mod m
代码如下：时间复杂度O(length(A) + length(B))
class Solution {
public boolean check(int index, String A, String B) {
for (int i = 0; i < B.length(); i++) {
if (A.charAt((i + index) % A.length()) != B.charAt(i)) {
return false;
}
}
return true;
}
public int repeatedStringMatch(String A, String B) {
int q = (B.length() - 1) / A.length() + 1;
// 素数
int p = 113;
int MOD = 1_000_000_007;
// 乘法逆模
int pInv = BigInteger.valueOf(p).modInverse(BigInteger.valueOf(MOD)).intValue();
// 计算字符串B的哈希值，时间复杂度 O(B.length())
long bHash = 0, power = 1;
for (int i = 0; i < B.length(); i++) {
bHash += power * B.codePointAt(i);
bHash %= MOD;
power = (power * p) % MOD;
}
// 计算字符串A的第一个子串哈希值，时间复杂度 O(B.length())
long aHash = 0; power = 1;
for (int i = 0; i < B.length(); i++) {
aHash += power * A.codePointAt(i % A.length());
aHash %= MOD;
power = (power * p) % MOD;
}
// 如果一个子串的哈希值与 B 的哈希值匹配，将该子串与 B 进行比较，时间复杂度 O(B.length())
if (aHash == bHash && check(0, A, B)) return q;
power = (power * pInv) % MOD;
// 利用前一个子串的计算结果哈希值来计算当前子串的哈希值
for (int i = B.length(); i < (q + 1) * A.length(); i++) {
aHash -= A.codePointAt((i - B.length()) % A.length());
aHash *= pInv;
aHash += power * A.codePointAt(i % A.length());
aHash %= MOD;
if (aHash == bHash && check(i - B.length() + 1, A, B)) {
return i < q * A.length() ? q : q + 1;
}
}
return -1;
}
}
