Sponsored
Sponsored
This approach involves repeating the string a incrementally and checking if b becomes a substring. The minimum length of repeated a needed should be at least equal to b's length. Thus, start by repeating a just enough times to get a string longer than b and check if b is a substring. If not, repeat a one more time to cover scenarios where b spans two a's boundary.
Time Complexity: O((m + n) * n), where m is the length of a and n is the length of b. Space Complexity: O(m + n).
1#include <iostream>
2#include <string>
3
4int repeatedStringMatch(std::string a, std::string b) {
5 int m = a.size(), n = b.size();
6 int repeat = (n + m - 1) / m;
7 std::string result;
8 for (int i = 0; i <= repeat + 1; ++i) {
9 if (result.find(b) != std::string::npos) return i;
10 result += a;
11 }
12 return -1;
13}
14
15int main() {
16 std::string a = "abcd";
17 std::string b = "cdabcdab";
18 std::cout << repeatedStringMatch(a, b) << std::endl;
19 return 0;
20}The solution calculates how many times a should minimally be repeated to cover b's length. Attempts to find b within progressively longer strings formed by concatenating a.
This approach relies on two repeated concatenations of string a. As per the pigeonhole principle, if b can fit within the repeated strings, it should certainly fit within two full concatenated repetitions and its prefix or suffix match.
Time Complexity: O(m * n). Space Complexity: O(m).
1#
Combines two copies of a and then checks
b within different starting indices, thus quickly determining the repetition count.