LeetCode 686 - Repeated String Match


https://leetcode.com/problems/repeated-string-match/description/
Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.
For example, with A = "abcd" and B = "cdabcdab".
Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").
Note:
The length of A and B will be between 1 and 10000.


As in Approach #1, we've reduced the problem to deciding whether B is a substring of some A * k. Using the following technique, we can decide whether B is a substring in O(len(A) * k) time.
Algorithm
For strings S, consider each S[i] as some integer ASCII code. Then for some prime p, consider the following function modulo some prime modulus \mathcal{M}:
\text{hash}(S) = \sum_{0 \leq i < len(S)} p^i * S[i]
Notably, \text{hash}(S[1:] + x) = \frac{(\text{hash}(S) - S[0])}{p} + p^{n-1} x. This shows we can get the hash of every substring of A * q in time complexity linear to it's size. (We will also use the fact that p^{-1} = p^{\mathcal{M}-2} \mod \mathcal{M}.)
However, hashes may collide haphazardly. To be absolutely sure in theory, we should check the answer in the usual way. The expected number of checks we make is in the order of 1 + \frac{s}{\mathcal{M}} where s is the number of substrings we computed hashes for (assuming the hashes are equally distributed), which is effectively 1.

  • Time Complexity: O(M+N) (at these sizes), where M, N are the lengths of strings A, B. As in Approach #1, we justify that A * (q+1) will be of length O(M + N), and computing the rolling hashes was linear work. We will also do a linear O(N) final check of our answer 1 + O(M) / \mathcal{M} times. In total, this is O(M+N + N(1 + \frac{M}{\mathcal{M}})) work. Since M \leq 10000 < \mathcal{M} = 10^9 + 7, we can consider this to be linear behavior.
  • Space complexity: O(1). Only integers were stored with additional memory.
    public boolean check(int index, String A, String B) {
        for (int i = 0; i < B.length(); i++) {
            if (A.charAt((i + index) % A.length()) != B.charAt(i)) {
                return false;
            }
        }
        return true;
    }
    public int repeatedStringMatch(String A, String B) {
        int q = (B.length() - 1) / A.length() + 1;
        int p = 113, MOD = 1_000_000_007;
        int pInv = BigInteger.valueOf(p).modInverse(BigInteger.valueOf(MOD)).intValue();

        long bHash = 0, power = 1;
        for (int i = 0; i < B.length(); i++) {
            bHash += power * B.codePointAt(i);
            bHash %= MOD;
            power = (power * p) % MOD;
        }

        long aHash = 0; power = 1;
        for (int i = 0; i < B.length(); i++) {
            aHash += power * A.codePointAt(i % A.length());
            aHash %= MOD;
            power = (power * p) % MOD;
        }

        if (aHash == bHash && check(0, A, B)) return q;
        power = (power * pInv) % MOD;

        for (int i = B.length(); i < (q + 1) * A.length(); i++) {
            aHash -= A.codePointAt((i - B.length()) % A.length());
            aHash *= pInv;
            aHash += power * A.codePointAt(i % A.length());
            aHash %= MOD;
            if (aHash == bHash && check(i - B.length() + 1, A, B)) {
                return i < q * A.length() ? q : q + 1;
            }
        }
        return -1;
    }
http://www.cnblogs.com/grandyang/p/7631434.html
这道题让我们用字符串B来匹配字符串A,问字符串A需要重复几次,如果无法匹配,则返回-1。那么B要能成为A的字符串,那么A的长度肯定要大于等于B,所以当A的长度小于B的时候,我们可以先进行重复A,直到A的长度大于等于B,并且累计次数cnt。那么此时我们用find来找,看B是否存在A中,如果存在直接返回cnt。如果不存在,我们再加上一个A,再来找,这样可以处理这种情况A="abc", B="cab",如果此时还找不到,说明无法匹配
https://leetcode.com/problems/repeated-string-match/discuss/108086/Java-Solution-Just-keep-building-(OJ-Missing-Test-Cases)
The idea is to keep string builder and appending until the length A is greater or equal to B.

The question can be summarized as "What is the smallest k for which B is a substring of A * k?" We can just try every k.
Algorithm
Imagine we wrote S = A+A+A+.... If B is to be a substring of S, we only need to check whether some S[0:], S[1:], ..., S[len(A) - 1:] starts with B, as S is long enough to contain B, and S has period at most len(A).
Now, suppose q is the least number for which len(B) <= len(A * q). We only need to check whether B is a substring of A * q or A * (q+1). If we try k < q, then B has larger length than A * q and therefore can't be a substring. When k = q+1A * k is already big enough to try all positions for B; namely, A[i:i+len(B)] == B for i = 0, 1, ..., len(A) - 1.
  • Time Complexity: O(N*(N+M)), where M, N are the lengths of strings A, B. We create two strings A * qA * (q+1) which have length at most O(M+N). When checking whether B is a substring of A, this check takes naively the product of their lengths.
  • Space complexity: As justified above, we created strings that used O(M+N) space.



 public int repeatedStringMatch(String A, String B) {

    int count = 0;
    StringBuilder sb = new StringBuilder();
    while (sb.length() < B.length()) {
        sb.append(A);
        count++;
    }
    if(sb.toString().contains(B)) return count;
    if(sb.append(A).toString().contains(B)) return ++count;
    return -1;
}
https://leetcode.com/problems/repeated-string-match/discuss/108090/Intuitive-Python-2-liner
Let n be the answer, the minimum number of times A has to be repeated.
For B to be inside AA has to be repeated sufficient times such that it is at least as long as B (or one more), hence we can conclude that the theoretical lower bound for the answer would be length of B / length of A.
Let x be the theoretical lower bound, which is ceil(len(B)/len(A)).
The answer n can only be x or x + 1 (in the case where len(B) is a multiple of len(A) like in A = "abcd" and B = "cdabcdab") and not more. Because if Bis already in A * nB is definitely in A * (n + 1).
Hence we only need to check whether B in A * x or B in A * (x + 1), and if both are not possible return -1.

X. KMP
https://leetcode.com/problems/repeated-string-match/discuss/108084/C++-4-lines-O(m-*-n)-or-O(1)-and-7-lines-KMP-O(m-+-n)-or-O(n)
This is basically a modified version of string find, which does not stop at the end of A, but continue matching by looping through A.
int repeatedStringMatch(string A, string B) {
    for (auto i = 0, j = 0; i < A.size(); ++i) {
        for (j = 0; j < B.size() && A[(i + j) % A.size()] == B[j]; ++j);
        if (j == B.size()) return (i + j) / A.size() + ((i + j) % A.size() != 0 ? 1 : 0);
    }
    return -1;
}
As suggested by @k_j, I am also providing O(n + m) version that uses a prefix table (KMP). We first compute the prefix table using the suffix and prefix pointers. Then we are going through A only once, shifting B using the prefix table.
This solution requires O(n) extra memory for the prefix table, but it's the fastest out there (OJ runtime is 3 ms). However, we do not need extra memory to append A multiple times, as in many other solutions.
Also thanks to @mylzsd for the review and the optimization to move i faster (skip multiple search characters) rather incrementing it one by one.
int repeatedStringMatch(string a, string b) {
    vector<int> prefTable(b.size() + 1); // 1-based to avoid extra checks.
    for (auto sp = 1, pp = 0; sp < b.size(); prefTable[++sp] = pp) {
        pp = b[pp] == b[sp] ? pp + 1 :  prefTable[pp];
    }
    for (auto i = 0, j = 0; i < a.size(); i += max(1, j - prefTable[j]), j = prefTable[j]) {
        while (j < b.size() && a[(i + j) % a.size()] == b[j]) ++j;
        if (j == b.size()) return (i + j) / a.size() + ((i + j) % a.size() != 0 ? 1 : 0);
    }
    return -1;
}
Since several users had this question, I am copying here a simple example demonstrating how the KMP algorithm uses the prefix table to skip previously matched prefixes.
A: aabaabaac
B: aabaac
We will start matching from A[i = 0] and B[j = 0], match "aabaa" and stop on B[j = 5] ('c' != 'b'). Without the prefix table, we will have to match again starting from A[i = 1] and B[j = 0].
The prefix table for A looks like this (it's 1-based to avoid extra checks): [0, 0, 1, 0, 1, 2, 3, 4, 5, 2].It tells us that we already matched "aa", and we can continue matching from A[i + j = 5] and B[j = 2].
i += max(1, j - prefTable[j]); i = 0 + 5 - prefTable[5] = 0 + 5 - 2 = 3;
j = prefTable[5] = 2;
A: aabaabaac
B: ___aabaac
https://leetcode.com/problems/repeated-string-match/discuss/108128/O(orAor-%2B-orBor)-time-Solution

    public int repeatedStringMatch(String A, String B) {
        StringBuilder builder = new StringBuilder(A);
        while (builder.length() < B.length())
            builder.append(A);

        int[] next = new int[B.length()];
        for (int i = 0, j = -1; i < B.length(); i++) {
            while (j != -1 && B.charAt(i) != B.charAt(j + 1))
                j = next[j];
            next[i] = i > 0 && B.charAt(i) == B.charAt(j + 1) ? j + 1 : -1;
            j = next[i];
        }

        for (int i = 0; i < 3; i++) {
            if (kmpMatch(builder.toString(), B, next))
                return builder.length() / A.length();
            builder.append(A);
        }
        return -1;
    }

    private boolean kmpMatch(String s, String pattern, int[] next) {
        for (int i = 0, j = -1; i < s.length(); i++) {
            while (j != -1 && s.charAt(i) != pattern.charAt(j + 1))
                j = next[j];
            if (s.charAt(i) == pattern.charAt(j + 1))
                j++;
            if (j == pattern.length() - 1)
                return true;
        }
        return false;
    }

下面这种解法还是由热心网友edyyy提供,没有用到字符串自带的find函数,而是逐个字符进行比较,循环字符串A中的所有字符,然后用个变量j,初始化为0,用来循环字符串B中的字符,每个字符和A中对应的字符进行比较,此时从A中取字符就要把A当作一个循环数组来处理,用(i+j)%m来取字符,还要确保j小于n,避免越界,如果字符匹配的话,j自增1。while 循环结束后,如果j等于n了,说明B中所有的字符都成功匹配了,那么我们来计算A的重复次数,通过(i+j-1)/m + 1来得到,注意i+j要减1再除以m,之后再加上一次。因为当i+j正好等于m时,说明此时不用重复A,那么(i+j-1)/m + 1还是等于1,当i+j>m的时候,需要重复A了,(i+j-1)/m + 1也可以得到正确的结构

    int repeatedStringMatch(string A, string B) {
        int m = A.size(), n = B.size();
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && A[(i + j) % m] == B[j]) ++j;
            if (j == n) return (i + j - 1) / m + 1;
        }
        return -1;
    }

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts