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

# Repeated String Match

<https://leetcode.com/problems/repeated-string-match/description/>

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

## Thoughts

如果B存在于由A组成的str中, 那么B应当是与A中第一个字符和之后的字符匹配, 或第二个字符开始的字符串匹配, 或第N个字符开始匹配. 即0, 1, ..., A.len - 1. 举个例子, A = abcd, B可以与分别以a, b, c, d为开头的拼接出来的字符串相匹配. 所以d和d后面应该能凑够至少与B等长字符串. 最终长度不超过A.len + B.len. 因为如果不与abcd为开头且长度为B的字符串匹配, 后面再贴无论多少, 也只是这些字符串的重复, 依然不会匹配.

## Code

```
class Solution {
    public int repeatedStringMatch(String A, String B) {
        StringBuilder sb = new StringBuilder(A);
        int i = 1;
        while (sb.length() < B.length() || !sb.toString().contains(B)) {
            if(sb.length() - A.length() > B.length()){
                return -1;
            }
            sb.append(A);
            i++;
        }

        return i;
    }
}
```

## Analysis

时间复杂度O(M/N \* N + MN) = O(MN).