686. Repeated String Match / Rabin Karp

Problem Statement

Given two strings a and b, return the minimum number of times you should repeat string a so that string b is 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

https://leetcode.com/problems/repeated-string-match/description/

Video Links

https://www.youtube.com/watch?v=Vff71v5b2V0&ab_channel=ADITYAPRAKASH

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;
    }
};

Approach 3:

C++

Approach 4:

C++

Similar Problems