-
Notifications
You must be signed in to change notification settings - Fork 0
/
Repeated String Match
71 lines (65 loc) · 2.05 KB
/
Repeated String Match
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
/*
LeetCode 686:
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").
Note:
The length of A and B will be between 1 and 10000.
Solution:
Language: C++
Tag:
*/
class Solution {
public:
int repeatedStringMatch(string A, string B) {
// 1. Rabin Karp
int step = 1;
string src = A;
while (src.length() < B.length()) {
src += A;
++step;
}
if (strStr2(src, B) == true) {
return step;
}
src += A; // "abcd" "cdabcdab"
++step;
if (strStr2(src, B) == true) {
return step;
}
return -1;
}
bool strStr2(string source, string target) {
int n = source.length(), m = target.length();
int Modulo = (int)pow(10.0, 6.0), Base = 31;
int power = 1, target_code = 0, source_code = 0;
int j = 0;
for (int i = 0; i < m; ++i) {
target_code = (target_code * Base + (int)target[i]) % Modulo;
power = (power * Base) % Modulo;
}
for (int i = 0; i < n; ++i) {
source_code = (source_code * Base + (int)source[i]) % Modulo;
if (i < m - 1) {
continue;
}
if (i >= m) {
source_code = source_code - ((int)source[i - m] * power) % Modulo;
if (source_code < 0) {
source_code += Modulo;
}
}
if (source_code == target_code) {
for (j = 0; j < m; ++j) {
if (source[i - m + j + 1] != target[j]) {
break;
}
}
if (j == m) {
return true;
}
}
}
return false;
}
};