# [LeetCode] 686. Repeated String Match 重复字符串匹配

2021年09月15日 阅读数：1

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.html

For example, with A = "abcd" and B = "cdabcdab".java

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").python

Note:
The length of `A` and `B` will be between 1 and 10000.app

Java: 1code

```class Solution {
public int repeatedStringMatch(String A, String B) {
StringBuilder sb = new StringBuilder();
sb.append(A);
int count = 1;
while(sb.indexOf(B)<0){
if(sb.length()-A.length()>B.length()){
return -1;
}
sb.append(A);
count++;
}

return count;
}　　```

Python: 1htm

```class Solution(object):
def repeatedStringMatch(self, A, B):
"""
:type A: str
:type B: str
:rtype: int
"""
sa, sb = len(A), len(B)
x = 1
while (x - 1) * sa <= 2 * max(sa, sb):
if B in A * x: return x
x += 1
return -1　```

Python: 3

```# Time:  O(n + m)
# Space: O(1)

class Solution(object):
def repeatedStringMatch(self, A, B):
"""
:type A: str
:type B: str
:rtype: int
"""
def check(index):
return all(A[(i+index) % len(A)] == c
for i, c in enumerate(B))

M, p = 10**9+7, 113
p_inv = pow(p, M-2, M)
q = (len(B)+len(A)-1) // len(A)

b_hash, power = 0, 1
for c in B:
b_hash += power * ord(c)
b_hash %= M
power = (power*p) % M

a_hash, power = 0, 1
for i in xrange(len(B)):
a_hash += power * ord(A[i%len(A)])
a_hash %= M
power = (power*p) % M

if a_hash == b_hash and check(0): return q

power = (power*p_inv) % M
for i in xrange(len(B), (q+1)*len(A)):
a_hash = (a_hash-ord(A[(i-len(B))%len(A)])) * p_inv
a_hash += power * ord(A[i%len(A)])
a_hash %= M
if a_hash == b_hash and check(i-len(B)+1):
return q if i < q*len(A) else q+1

return -1　　```

C++: 1

```int repeatedStringMatch(string A, string B) {
for (auto i = 0, j = 0; i < A.size(); ++i) {
for (j = 0; j < B.size() && A[(i + j) % A.size()] == B[j]; ++j);
if (j == B.size()) return (i + j) / A.size() + ((i + j) % A.size() != 0 ? 1 : 0);
}
return -1;
}
```

C++: 2

```int repeatedStringMatch(string a, string b) {
vector<int> prefTable(b.size() + 1); // 1-based to avoid extra checks.
for (auto sp = 1, pp = 0; sp < b.size(); ) {
if (b[pp] == b[sp]) prefTable[++sp] = ++pp;
else if (pp == 0) prefTable[++sp] = pp;
else pp = prefTable[pp];
}
for (auto i = 0, j = 0; i < a.size(); i += max(1, j - prefTable[j]), j = prefTable[j]) {
while (j < b.size() && a[(i + j) % a.size()] == b[j]) ++j;
if (j == b.size()) return (i + j) / a.size() + ((i + j) % a.size() != 0 ? 1 : 0);
}
return -1;
}
```

C++:

```class Solution {
public:
int repeatedStringMatch(string A, string B) {
string t = A;
for (int i = 1; i <= B.size() / A.size() + 2; ++i) {
if (t.find(B) != string::npos) return i;
t += A;
}
return -1;
}
};
```

C++:

```class Solution {
public:
int repeatedStringMatch(string A, string B) {
int m = A.size(), n = B.size();
for (int i = 0; i < m; ++i) {
int j = 0;
while (j < n && A[(i + j) % m] == B[j]) ++j;
if (j == n) return (i + j - 1) / m + 1;
}
return -1;
}
};
```

[LeetCode] 459. Repeated Substring Pattern 重复子字符串模式