Given two strings a and b, return the minimum number of times you should repeat string a so that stringbis a substring of it. If it is impossible for b to be a substring of a after repeating it, return -1.
Notice: string "abc" repeated 0 times is "", repeated 1 time is "abc" and repeated 2 times is "abcabc".
Example 1:
Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.
Example 2:
Input: a = "a", b = "aa"
Output: 2
Constraints:
1 <= a.length, b.length <= 104
a and b consist of lowercase English letters.
Intuition
Approach 1:
a = 'abcd'
b = 'cd abcd ab'
b =
a = 'abcd'
b='cd abcd ab'
b = prefix + n*a + suffix => cd (abcd) ab ==> n+2
b = prefix + n*a => cd (abcd) ==> n+1
b = n*a + suffix => (abcd) ab ==> n+1
b=n*a => (abcd) ==> n
Basically
We take lenb/lena and generate the n*a part and
Later check for other conditions by adding the strings seperately
But this npos find takes n*m time
Approach 2: Rabin Karp
Rolling hash concept
Average(m+n) case Time
Refer - Abdul Bari Video for more
Links
Video Links
Approach 1:
Intution : npos find
n*m
C++
class Solution {
public:
int repeatedStringMatch(string a, string b) {
int len_a = a.size();
int len_b = b.size();
int n = len_b/len_a;
int count = n;
string temp = "";
while(count--){
temp = temp + a;
}
if(temp.find(b) != string::npos)
return n;
temp += a;
if(temp.find(b) != string::npos)
return n+1;
temp += a;
if(temp.find(b) != string::npos)
return n+2;
return -1;
}
};
Approach 2:
Rabin Karp
C++
class Solution {
private:
int BASE = 1000000;
public:
int repeatedStringMatch(string A, string B) {
if(A == B) return 1;
int count = 1;
string source = A;
while(source.size() < B.size()){
count++;
source+=A;
}
if(source == B) return count;
if(Rabin_Karp(source,B) != -1) return count;
if(Rabin_Karp(source+A,B) != -1) return count+1;
return -1;
}
int Rabin_Karp(string source, string target){
if(source == "" or target == "") return -1;
int m = target.size();
int power = 1;
for(int i = 0;i<m;i++){
power = (power*31)%BASE;
}
int targetCode = 0;
for(int i = 0;i<m;i++){
targetCode = (targetCode*31+target[i])%BASE;
}
int hashCode = 0;
for(int i = 0;i<source.size();i++){
hashCode = (hashCode*31 + source[i])%BASE;
if(i<m-1) continue;
if(i>=m){
hashCode = (hashCode-source[i-m]*power)%BASE;
}
if(hashCode<0)
hashCode+=BASE;
if(hashCode == targetCode){
if(source.substr(i-m+1,m) == target)
return i-m+1;
}
}
return -1;
}
};