[Medium] 686. Repeated String Match

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

Thinking Process

Notice: String "abc" repeated 0 times is "", repeated 1 time is "abc", and repeated 2 times is "abcabc".

Identify the pattern from constraints (sorted? graph? optimal substructure?).
Write brute force first mentally, then optimize the bottleneck.
Verify edge cases: empty input, single element, duplicates.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Brute force (this problem)	Often O(n^2) or O(2^n)	O(n)	Baseline; clarifies the optimization target
Sort + scan	O(n log n)	O(1)	Pairs, intervals, greedy ordering
Hash map / set	O(n)	O(n)	Frequency, membership, two-sum style
Single-pass linear	O(n)	O(1)	Two pointers, sliding window, Kadane

Examples

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

Example 3:

Input: a = "a", b = "a"
Output: 1

Example 4:

Input: a = "abc", b = "wxyz"
Output: -1

Constraints

1 <= a.length, b.length <= 10^4
a and b consist of lowercase English letters.

String Matching Algorithms

Knuth-Morris-Pratt (KMP) Algorithm

KMP is an efficient string-searching algorithm that preprocesses the pattern to create a prefix function (also called LPS - Longest Proper Prefix which is also a Suffix). This allows skipping unnecessary comparisons.

Key Concepts:

Prefix Function (π/LPS): For each position i in pattern, π[i] is the length of the longest proper prefix that is also a suffix of pattern[0..i]
No Backtracking: When a mismatch occurs, we don’t reset to the beginning but use the prefix function to determine the next position
Time Complexity: O(n + m) where n = text length, m = pattern length

How KMP Works:

Preprocessing Phase: Build prefix function for pattern
- For each position, find longest prefix-suffix match
- Use previous values to compute current value efficiently
Search Phase: Match pattern in text
- Compare characters from left to right
- On mismatch, use prefix function to skip ahead
- Never backtrack in text

Prefix Function Example:

For pattern "ababaca":

Pattern:  a  b  a  b  a  c  a
Index:     0  1  2  3  4  5  6
π[i]:     0  0  1  2  3  0  1

Explanation:
- π[0] = 0 (no proper prefix)
- π[1] = 0 ("ab" has no prefix-suffix match)
- π[2] = 1 ("aba" has "a" as prefix-suffix)
- π[3] = 2 ("abab" has "ab" as prefix-suffix)
- π[4] = 3 ("ababa" has "aba" as prefix-suffix)
- π[5] = 0 ("ababac" has no prefix-suffix match)
- π[6] = 1 ("ababaca" has "a" as prefix-suffix)

Rabin-Karp Algorithm

Rabin-Karp uses rolling hash to efficiently compute hash values for substrings. It compares hash values first, then verifies with character-by-character comparison if hashes match.

Key Concepts:

Rolling Hash: Compute hash of substring in O(1) time using previous hash
Hash Function: Use polynomial rolling hash: hash = (hash * base + char) % mod
Collision Handling: When hashes match, verify with actual string comparison
Time Complexity: Average O(n + m), worst case O(n × m) if many hash collisions

How Rabin-Karp Works:

Precompute Pattern Hash: Calculate hash of pattern string
Rolling Hash in Text:
- Compute hash of first window
- Slide window and update hash in O(1)
- Compare hashes, verify if match
Base and Modulo: Use large base and prime modulo to reduce collisions

Rolling Hash Formula:

For substring s[i..i+m-1]:
hash = (s[i] * base^(m-1) + s[i+1] * base^(m-2) + ... + s[i+m-1]) % mod

To slide window from i to i+1:
new_hash = ((old_hash - s[i] * base^(m-1)) * base + s[i+m]) % mod

KMP Template

Here’s the general template for KMP algorithm:

class KMP {
private:
    // Build prefix function (LPS array)
    vector<int> buildPrefixFunction(const string& pattern) {
        int m = pattern.size();
        vector<int> pi(m, 0);
        
        for(int i = 1, j = 0; i < m; i++) {
            // Mismatch: backtrack using prefix function
            while(j > 0 && pattern[i] != pattern[j]) {
                j = pi[j - 1];
            }
            // Match: extend prefix
            if(pattern[i] == pattern[j]) {
                j++;
            }
            pi[i] = j;
        }
        return pi;
    }
    
public:
    // Search for pattern in text
    int search(const string& text, const string& pattern) {
        int n = text.size(), m = pattern.size();
        if(m == 0) return 0;
        
        vector<int> pi = buildPrefixFunction(pattern);
        
        for(int i = 0, j = 0; i < n; i++) {
            // Mismatch: use prefix function to skip
            while(j > 0 && text[i] != pattern[j]) {
                j = pi[j - 1];
            }
            // Match: advance both pointers
            if(text[i] == pattern[j]) {
                j++;
            }
            // Pattern found
            if(j == m) {
                return i - m + 1; // Return starting index
            }
        }
        return -1; // Not found
    }
};

Key Template Components:

Prefix Function (π/LPS):
- pi[i] = longest prefix-suffix length for pattern[0..i]
- Built in O(m) time
Search Algorithm:
- No backtracking in text
- Use prefix function to skip on mismatch
- Time complexity: O(n + m)
Circular Matching:
- Use i % n for circular text
- Adjust loop condition: i - j < n

Rabin-Karp Template

Here’s the general template for Rabin-Karp algorithm:

class RabinKarp {
private:
    const long long BASE = 256;
    const long long MOD = 1e9 + 7;
    
    long long computeHash(const string& s, int start, int len) {
        long long hash = 0;
        for(int i = 0; i < len; i++) {
            hash = (hash * BASE + s[start + i]) % MOD;
        }
        return hash;
    }
    
    long long updateHash(long long oldHash, char remove, char add, long long power) {
        oldHash = (oldHash - (remove * power) % MOD + MOD) % MOD;
        oldHash = (oldHash * BASE + add) % MOD;
        return oldHash;
    }
    
public:
    int search(const string& text, const string& pattern) {
        int n = text.size(), m = pattern.size();
        if(m == 0) return 0;
        if(n < m) return -1;
        
        // Precompute pattern hash
        long long patternHash = computeHash(pattern, 0, m);
        
        // Precompute BASE^(m-1) for rolling hash
        long long power = 1;
        for(int i = 0; i < m - 1; i++) {
            power = (power * BASE) % MOD;
        }
        
        // Initial window hash
        long long textHash = computeHash(text, 0, m);
        
        // Check first window
        if(textHash == patternHash) {
            if(text.substr(0, m) == pattern) return 0;
        }
        
        // Rolling hash: slide window
        for(int i = 1; i <= n - m; i++) {
            textHash = updateHash(textHash, text[i-1], text[i+m-1], power);
            
            if(textHash == patternHash) {
                if(text.substr(i, m) == pattern) return i;
            }
        }
        
        return -1;
    }
};

Key Template Components:

Hash Function:
- Polynomial rolling hash: hash = (hash * BASE + char) % MOD
- BASE = 256 (for ASCII), MOD = large prime
Rolling Hash:
- Update hash in O(1) when sliding window
- Remove left char, add right char
Collision Handling:
- Always verify hash matches with actual string comparison
- Prevents false positives

Complexity

Solution 1: KMP

Time Complexity: O(n + m)

Prefix function: O(m) - build LPS array
Search phase: O(n) - each character visited at most twice
Total: O(n + m) where n = a.length, m = b.length

Space Complexity: O(m)

Prefix function array: O(m)
Total: O(m)

Solution 2: Rabin-Karp

Time Complexity: O(n + m) average, O(n × m) worst case

Hash computation: O(m) for pattern
Rolling hash: O(n) for text (O(1) per window)
Verification: O(m) per hash match (rare collisions)
Total: O(n + m) average, O(n × m) worst case with many collisions

Space Complexity: O(1)

Hash variables: O(1)
Total: O(1) excluding input strings

Key Points

KMP is Optimal: Guaranteed O(n + m) time, no worst-case degradation
Rabin-Karp: Average O(n + m), but can degrade with hash collisions
Circular Matching: Use modulo arithmetic for repeated strings
Minimum Repetitions: At least ⌈b.length / a.length⌉, at most ⌈b.length / a.length⌉ + 1
Prefix Function: Key to KMP’s efficiency - avoids backtracking
Rolling Hash: Key to Rabin-Karp’s efficiency - O(1) hash updates

Comparison: KMP vs Rabin-Karp

Aspect	KMP	Rabin-Karp
Time Complexity	O(n + m) guaranteed	O(n + m) average, O(n × m) worst
Space Complexity	O(m)	O(1)
Preprocessing	O(m) for prefix function	O(m) for pattern hash
Backtracking	None (no text backtracking)	None (sliding window)
Collision Handling	Not needed	Required (verify matches)
Implementation	More complex	Simpler
Recommended	✅ Yes (guaranteed performance)	⚠️ Good for average case

Key Takeaways

Notice:** String "abc" repeated 0 times is "", repeated 1 time is "abc", and repeated 2 times is "abcabc".
Identify the pattern from constraints (sorted? graph? optimal substructure?).
Write brute force first mentally, then optimize the bottleneck.

References

LC 686: Repeated String Match on LeetCode
LeetCode Discuss — LC 686: Repeated String Match
LeetCode Editorial (may require premium)

Common Mistakes

Skipping edge cases (empty input, single element, boundaries).
Off-by-one errors in loops and index ranges.
Forgetting to handle the case when no valid answer exists.

28. Find the Index of the First Occurrence in a String - KMP application
214. Shortest Palindrome - KMP for palindrome
1392. Longest Happy Prefix - Prefix function
187. Repeated DNA Sequences - Rolling hash

Robina Li

[Medium] 686. Repeated String Match

Thinking Process

Common Approaches

Examples

Constraints

String Matching Algorithms

Knuth-Morris-Pratt (KMP) Algorithm

Key Concepts:

How KMP Works:

Prefix Function Example:

Rabin-Karp Algorithm

Key Concepts:

How Rabin-Karp Works:

Rolling Hash Formula:

KMP Template

Key Template Components:

Rabin-Karp Template

Key Template Components:

Complexity

Solution 1: KMP

Solution 2: Rabin-Karp

Key Points

Comparison: KMP vs Rabin-Karp

Key Takeaways

References

Common Mistakes

Tags

Related Posts

Recent Posts

Thinking Process

Common Approaches

Examples

Constraints

String Matching Algorithms

Knuth-Morris-Pratt (KMP) Algorithm

Key Concepts:

How KMP Works:

Prefix Function Example:

Rabin-Karp Algorithm

Key Concepts:

How Rabin-Karp Works:

Rolling Hash Formula:

KMP Template

Key Template Components:

Rabin-Karp Template

Key Template Components:

Complexity

Solution 1: KMP

Solution 2: Rabin-Karp

Key Points

Comparison: KMP vs Rabin-Karp

Key Takeaways

References

Common Mistakes

Related Problems

Tags

Related Posts

Recent Posts