> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/string/kmp/686-repeated-string-match.md).

# 686 Repeated String Match

## 686. [Repeated String Match](https://leetcode.com/problems/repeated-string-match/description/)

## 1. Question

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.

## 2. Implementation

**(1) Brute Force**

思路：如果A要包含B的话，那么A的长度必须大于等于B, 所以我们不断重复A，直到它的长度大于等于B。如果A此时包含B，则返回重复A的次数count，如果还不包含，比如A = "abc", B = "cab"这种形式，说明A的长度等于B，但刚好B是A的rotation，所以我们再重复A多一次，然后判断是否含有B. A长度大于B时，仍然不包含B，则返回-1

```java
class Solution {
    public int repeatedStringMatch(String A, String B) {
        int count = 0;

        StringBuilder sb = new StringBuilder();

        while (sb.length() < B.length()) {
            sb.append(A);
            ++count;
        } 

        if (sb.toString().indexOf(B) >= 0) {
            return count;
        }

        if (sb.append(A).toString().indexOf(B) >= 0) {
            return count + 1;
        }
        return -1;
    }
}
```

## 3. Time & Space Complexity

**Brute Force**: 时间复杂度O(m/n), m是B的长度, n是A的长度，空间复杂度O(m)