[Geeks for Geeks] Repeated String Match

Repeated String Match

Given two strings A and B, find the minimum number of times A has to be repeated such that B becomes a substring of the repeated A. If B cannot be a substring of A no matter how many times it is repeated, return -1.

  • Time : O(n + m)
  • Space : O(min(n, 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
37
38
39
40
41
42
43
44
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 repeatedStringMatch(string A, string B) {
int n = A.length(), m = B.length();
if(n == m) return A == B ? 1 : -1;
if(n > m) return kmp(A, B) != -1 ? 1 : kmp(A + A, B) != -1 ? 2 : -1;
int pos = kmp(B, A);
if(pos == -1) return -1;
int left = pos - n;
if(left >= n) return -1;
int res = 1 + (left >= 0);
for(int i = n - 1; i >= 0 and left >= 0; i--, left--) {
if(A[i] != B[left]) return -1;
}
for(int i = pos + 1, j = 0; i < m; i++) {
if(j == 0) res++;
if(A[j] != B[i]) return -1;
j = (j + 1) % n;
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/26/PS/GeeksforGeeks/repeated-string-match/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.