# 686. Repeated String Match / Rabin Karp

## Problem Statement

<br>

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"`.

&#x20;

**Example 1:**

<pre><code><strong>Input: a = "abcd", b = "cdabcdab"
</strong><strong>Output: 3
</strong><strong>Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: a = "a", b = "aa"
</strong><strong>Output: 2
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= a.length, b.length <= 104`
* `a` and `b` consist of lowercase English letters.

## Intuition

<pre><code>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
<strong>b=n*a => (abcd) ==> n
</strong>
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
</code></pre>

### 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
```

{% code title="C++" lineNumbers="true" %}

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

{% endcode %}

### Approach 2:

```
Rabin Karp
```

{% code title="C++" lineNumbers="true" %}

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

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###