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 <stdio.h>
2#include <string.h>
3
4int repeatedStringMatch(char * a, char * b) {
5 int m = strlen(a), n = strlen(b);
6 int repeat = (n + m - 1) / m, i;
7 char *result = (char *)malloc(m * (repeat + 1) + 1);
8 result[0] = '\0';
9 for(i = 0; i < repeat + 1; i++) {
10 strcat(result, a);
11 if (strstr(result, b) != NULL) {
12 free(result);
13 return i + 1;
14 }
15 }
16 free(result);
17 return -1;
18}
19
20int main() {
21 char a[] = "abcd";
22 char b[] = "cdabcdab";
23 printf("%d\n", repeatedStringMatch(a, b));
24 return 0;
25}The solution calculates the number of repetitions needed by dividing n (the length of b) by m (the length of a) rounded up. It creates a new string by repeatedly concatenating a and checks if b is a substring. If not found initially, it adds one more repetition as a final attempt.
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#include <iostream>
#include <string>
int repeatedStringMatch(std::string a, std::string b) {
int m = a.size(), n = b.size();
int repeat = (n + m - 1) / m;
std::string doubled = a + a;
for (int i = 0; i < repeat; ++i) {
if (doubled.substr(i) + a).find(b) != std::string::npos) return i + 1;
}
return -1;
}
int main() {
std::string a = "abcd";
std::string b = "cdabcdab";
std::cout << repeatedStringMatch(a, b) << std::endl;
return 0;
}The solution effectively utilizes the doubled string to check for presence of b, reducing the calculations involved.