[Geeks for Geeks] Minimum times A has to be repeated such that B is a substring of it

Minimum times A has to be repeated such that B is a substring of it

Given two strings A and B. Find minimum number of times A has to be repeated such that B is a Substring of it. If B can never be a substring then return -1.

  • Time : O(m)
  • Space : O(m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
vector<int> PI(string& s) {
int n = s.length();
vector<int> pi(n);
for(int i = 1, j = 0; i < n; i++) {
while(j > 0 and s[i] != s[j]) j = pi[j - 1];
if(s[i] == s[j]) pi[i] = ++j;
}

return pi;
}
int kmp(string s, string& t) {
int n = s.length(), m = t.length();
vector<int> pi = PI(t);
for(int i = 0, j = 0; i < n; i++) {
while(j > 0 and s[i] != t[j]) j = pi[j - 1];
if(s[i] == t[j]) {
if(++j == m)
return i;
}
}

return -1;
}
public:
int minRepeats(string A, string B) {
string s = "";
int res = 0;
while(s.length() < B.length()) {
s += A;
res++;
}

return kmp(s, B) != -1 ? res : kmp(s + A, B) != -1 ? res + 1 : -1;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/26/PS/GeeksforGeeks/minimum-times-a-has-to-be-repeated-such-that-b-is-a-substring-of-it/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.