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

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

``````class Solution {
public:
int repeatedStringMatch(string A, string B) {
int n1 = A.size(), n2 = B.size(), cnt = 1;
string t = A;
while (t.size() < n2) {
t += A;
++cnt;
}
if (t.find(B) != string::npos) return cnt;
t += A;
return (t.find(B) != string::npos) ? cnt + 1 : -1;
}
};
``````

``````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;
}
};
``````

``````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;
}
};
``````

Repeated Substring Pattern

https://discuss.leetcode.com/topic/105579/c-4-lines-o-m-n-o-1-and-8-lines-kmp-o-m-n-o-n

https://discuss.leetcode.com/topic/105566/java-solution-just-keep-building-oj-missing-test-cases

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation