RepeatedStringMatch [source code]

public class RepeatedStringMatch {
static
/******************************************************************************/
class Solution {
    public int repeatedStringMatch(String A, String B) {
        StringBuilder sb = new StringBuilder (A);
        while (sb.length () < B.length ())
            sb.append (A);
        if (!sb.toString ().contains (B))
            sb.append (A);
        String res = sb.toString ();
        return res.contains (B) ? res.length () / A.length () : -1;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        RepeatedStringMatch.Solution tester = new RepeatedStringMatch.Solution();
    }
}

题目看起来很简单, 但是其实并没有什么好的思路; 核心问题是, 怎么判断fail这个情况, 不可能无限循环下去;

感觉还是要自己简单升级, 总结点东西出来, 先动笔随便画画看, 看看能不能看到点什么规律; 不要害怕, 大胆的假设以及证伪;

想了半天没有特别好的突破口, 准备随便写写看: 对于背后的算法尤其是正确性的证明完全没有概念, 寄希望于先写一点代码出来好了;

完全没有想到的是, 直接一次就AC了, 耗时不到15分钟; 速度是160ms (77%);

what if you are clueless?

实际面试的时候, 很多时候就是这样, 很难说你这个题目你就知道一个连怎样证明correctness都已经很清楚的解法; 这种时候, 你不能站在那里发呆, take a calculated guess, then start writing code;

这题我本身是没有任何合理的想法的, 我最后开始写代码的时候, 其实是一点根据都没有的, 我的想法就很简单, As如果长度小于B, 那么肯定是不行的, 所以先multiply到这个长度为止, 然后检查一下是否成功, 如果不成功, 再多加一个A, 如果还不成功那么后面再加就肯定也不会成功;

这个claim我暂时是还没有想到怎么证明的: if N As is longer than B, and N As does not contain B, then (N+1) As won't contain B either. 如果这个成立, 那么很容易induction到任何比N大的M上面去;

事实上, 这个好像很好证明: contradiction就行了, 假如NA不包含B (0..(N-1)), 但是(N+1)A就包含B, 那么B肯定位于(1..N)A的范围内, 但是这个范围其实跟原来的(0..(N-1))A是完全相同的, 所以没有理由刚才不行, 现在就行了;

editorial1:

Intuition

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+1, A * 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. 

class Solution {  
    public int repeatedStringMatch(String A, String B) {  
        int q = 1;  
        StringBuilder S = new StringBuilder(A);  
        for (; S.length() < B.length(); q++) S.append(A);  
        if (S.indexOf(B) >= 0) return q;  
        if (S.append(A).indexOf(B) >= 0) return q+1;  
        return -1;  
    }  
}

思路跟我其实是一样的;

另外, 这个算法的复杂度, 很大程度上要取决于java的string的contains是怎么实现的; 如果是naive的做法, 就是A*B, 但是如果是KMP这样的, 就是线性的O(A + B); 查了一下, JDK好像还真的不是用的KMP: https://stackoverflow.com/questions/19543547/why-jdks-string-indexof-does-not-use-kmp

editorial2: 看来这题好像是有数学解法的; 不对, 根本不是数学解法, 其实就是他想要解决contains的速度问题: https://leetcode.com/articles/repeated-string-match/ 

import java.math.BigInteger;  

class Solution {  
    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;  
    }  
}

懒得看了, 有时间再说; 不过总体思路还是稍微有点了解: 按照他这个hash的计算方法, 只要A包含B, 那么就可以判断他们的hash之间的规律, 具体的介绍: https://www.geeksforgeeks.org/searching-for-patterns-set-3-rabin-karp-algorithm/

在geeks4geeks上面, 这个RK算法是跟KMP放在一个类别里面讲的; 所以还是有点意思的;

这个是discussion上面一个非常有意思的解法:

@votrubac said in C++ 4 lines O(m * n) | O(1) and 7 lines KMP O(m + n) | 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;  
}

这个解法的优势在于, 不需要正儿八经的把multiple给build出来, 直接就用mod来完成一个wrap的操作; 这个作者的洞察力很强; 整个算法的数学总结度也很高;

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

后面KMP的部分没有看懂, 不过听他自己说, 是受这个解法的影响:

@mylzsd said in C++ 4 lines O(m * n) | O(1) and 7 lines KMP O(m + n) | O(n):

@votrubac I've made some modification on prefix table construction (If there isn't a match and the lower pointer isn't 0, nothing should be added to prefix table) as well as searching based on your codes. And it is able to skip multiple searched characters rather than incrementing one at each time. Here are the modified c++ code and my Java version. 

class Solution {  
    public:  
        int repeatedStringMatch(string a, string b) {  
        vector<int> prefTable(b.size());  
        for (auto sp = 1, pp = 0; sp < b.size(); ) {  
            if (b[pp] == b[sp]) prefTable[sp++] = ++pp;  
            else if (pp == 0) sp++;  
            else pp = prefTable[pp - 1];  
        }  
        for (auto i = 0, j = 0; i < a.size(); i += j - prefTable[j - 1], j = prefTable[j - 1]) {  
            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);  
            if (j == 0) j++;  
        }  
        return -1;  
    }  
};

class Solution {  
    public int repeatedStringMatch(String A, String B) {  
        int[] prefix = new int[B.length()];  
        for (int i = 1, j = 0; i < B.length(); ) {  
            if (B.charAt(i) == B.charAt(j)) prefix[i++] = ++j;  
            else if (j == 0) i++;  
            else j = prefix[j - 1];  
        }  
        for (int i = 0, j = 0; i < A.length(); i += j - prefix[j - 1], j = prefix[j - 1]) {  
            while (j < B.length() && A.charAt((i + j) % A.length()) == B.charAt(j)) j++;  
            if (j == B.length()) return (int)Math.ceil((double)(i + j) / A.length());  
            if (j == 0) j++;  
        }  
        return -1;  
    }  
}

暂时不是太看得懂他们这个解法, 不过他们的KMP算法代码如此之短, 感觉可以适当记忆一下;

KMP这个东西反正是躲不过去的, 明天白天专门看一下这个算法, 然后再来重新消化一下他们这个算法; 好像discussion里面用KMP的算法相当的多;

大概熟悉了一下KMP的算法, 这个人LPS的计算算法有所改写, 但是实质上都是一样的;

但是他这里的search算法的写法其实跟geeks4geeks给出的标准写法有所差别:

  • 他这里的j更多的像是一个offset一样的东西, 所以最后比较的是[i+j] and [j]而不是[i] and [j]; 对应的, i和j的更新方式也要稍微有所改变, 不过改变不是很大;
  • geeks4geeks的写法, 应用了conditional advance的技巧, 也就是有些iteration, 只完成了j的退步, 而对i完全没有改变. 这里他这个写法用的是一个alternative, 也就是nested advance, 看起来类似两重循环的一个写法; 两个写法哪个更好我也不好说, 不过可以看到他这个代码还是写的很简练的;

仔细思考了一下他这个算法其他方面与标准写法的差别, 发现三个需要解决的问题:

  • 他header里面i += j - prefix[j - 1], j = prefix[j - 1]这个到底是什么操作?
    • 盯着代码看是看不懂的, 最后还是自己笔算看看; 严格来说没有针对一个case进行trace, 而是就是抽象的去画一画他这个算法的内容; 实际上最后发现这个东西不难理解; 当while循环结束之后, 假设没有成功, 那么这个时候按照geeks4geeks写法, 要么是advance i, 要么是backoff j; 而他header里面完成的就是这一点; 为了便于理解, 我们记下一个iteration(increment更新后的)i和j为i' and j', 那么有i' = i + j - lps, j' = lps. 这样保证了一个结果: i' + j' = i + j, 也就是类似于geeks4geeks写法里面, 当可以backoff j的时候, text里面的位置不改变; 自己可以画图理解一下到底为什么要这样;
  • 另外一个问题: if (j == 0) j++;完成的到底是什么?
    • 其实这个就是完成了类似上面的advance i的操作; 注意, 这里虽然看起来是++了j, 但是这个+的1最后只参与了i'的计算过程; 类似上面的分析, 最后完成的结果是`i' + j' = i + j + 1';
      • 实际上比这个稍微复杂一点, 你要参考geeks4geeks写法的那个版本来看: 当我们出现j等于0的时候, 我们应该advance在A里面的位置. 这里其实利用了一个小细节, 就是lps[0] = 0, 这样最后当j等于0的时候, 我们首先让j等于1, 然后我们做i += 1 - lps[0], 其实就是i++, 然后j = lps[0] = 0, 所以最后得到的正好就是i向前进了1, j归零;
  • @votrubac 认为这个算法只对A进行一个pass;
    • 其实这个是有所争议的, 因为里面的while循环里面是可能wrap很多次的; 不过你还是要理解一个问题, 为什么外层循环判断的是i < A.length ()? 要知道, i对应的其实是不同的window的start位置(in text), 所以总共其实就只有这么多的start位置, 走一遍就足够了; 这个可能也是他这里为什么选择改变i和j的定义的原因: 这样更容易判断这个1pass的结束时间点;
    • 下面带来的一个新问题就是, 假如还是用geeks4geeks标准写法, 那么我们怎么判断循环结束条件? 没有办法这样简单的通过限制window start的移动范围来进行一个terminate了, 好像只能用类似之前老算法那样, 判断长度关系, 也就是i移动的距离跟A, B的长度之间的关系来进行一个terminate的判断了; 这样看来, 也许人家之所以选择这样定义i和j就是因为看到了这个题目在允许wrap的前提下, 新增的一些难度;

总体来说这个是一个非常优秀的解法, 对于KMP的展示非常的elegant, 而且当我刚刚想到用KMP来做这个题目的时候, 我想的其实是改变contains的implementation而已, 其他的地方不改变, 但是他们这里用的方法其实更先进, 他们直接就把KMP整个都给incorporate进去了;

这个是另外一个用了KMP的解法:

@lixx2100 said in O(|A| + |B|)-time Solution:

Assume the repeated string does exist. Then, we must have
B = [some nullable suffix of A] AA..AA [some nullable prefix of A].

Let k = floor(|B| / |A|). Then, we just need to test
1) whether the string by repeating A k times contains B as a substring,
2) whether the string by repeating A (k+1) times contains B as a substring,
3) whether the string by repeating A (k+2) times contains B as a substring.

Note that, test 1 makes sense only if |B| is divisible by |A|. But for convenience, we include this case anyway, without increasing the overall asymptotic runtime.

Each test can be done in O(|A| + |B|) time using (say) KMP. Therefore, the total runtime is still O(|A| + |B|).

Java code: 

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

    for (int i = 0; i < 3; i++) {  
        if (builder.toString().contains(B)) // For simplicity, pretend that String.contains is implemented using KMP.  
            return builder.length() / A.length();  
        builder.append(A);  
    }  
    return -1;  
}

Using KMP: 

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

这个就是比较naive的使用KMP的方法, 并没有整个incorporate进去, 而且这个解法也没有成功避免由append造成的空间cost;

submission最优解:4(99), 非常的快, KMP的做法其实只做到了10(90): 

class Solution {  
    public int repeatedStringMatch(String A, String B) {  
        if (B.length() <= A.length() + 1) {  
            if (A.contains(B)) return 1;  
            else {  
                String A2 = A + A;  
                if (A2.contains(B)) return 2;  
            }  
            return -1;  
        }  

        char[] cb = B.toCharArray(), ca = A.toCharArray();  
        int lena = ca.length, lenb = cb.length, start = 0, nrepeat = -1;  
        while (start < lenb) {  
            if (cb[start] == ca[0]) {  
                if (start >= lena)  
                    return -1;  
                int len = 1;  
                while (start + len < lenb) {  
                    if (cb[start + len] == ca[len % lena])  
                        len++;  
                    else  
                        return -1;  
                }  
                if (len % lena == 0)  
                    nrepeat = len / lena;  
                else  
                    nrepeat = 1 + len / lena;  
                if (start != 0) {  
                    int n = 1;  
                    while (start - n >= 0) {  
                        if (cb[start - n] != ca[lena - n]) return -1;  
                        n++;  
                    }  
                    nrepeat++;  
                }  
                break;  
            }  
            start++;  
        }  
        return nrepeat;  
    }  
}

这个算法刚拿到手的时候也是完全看不懂, 只能笔算trace, 直接就用的题目给的这个case, 好在这个算法的trace倒是不难计算; 跑一遍之后大概理解了这个算法的思路; 这个算法有两个有趣的地方:

  • 类似之前discussion看到的KMP算法, 这个算法其实也是讲需要的循环长度降低到了最低;
  • 笔算的时候发现, 对于cb[start] == ca[0]的判断非常的有玄机; 这个算法跟普通的算法, 包括KMP算法, 也就是discussion里面的大部分的算法一个最大的区别在于, 这个算法看上去并不像是在NA里面找B, 而是在B里找NA; 找到了之后, 在B里面找到了一个NA的开始位置之后, 向前向后扫描来保证完全匹配就行了;

那么一个问题来了, 为什么这个问题可以用find NA in B的思路来做? 笔算了一下, 没有找到什么特别严谨的说法, 不过在纸面上来看, 这个做法是合理的; 基本上就是找到类似multiple位置的分界点, 然后从这个分界点的位置进行向后然后向前的扫描就行了;

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

Difficulty:Easy
Total Accepted:17K
Total Submissions:49.5K
Contributor:1337c0d3r
Companies
google
Related Topics
string
Similar Questions
Repeated Substring Pattern

results matching ""

    No results matching ""