C++ 4 lines O(m * n) | O(1) and 7 lines KMP O(m + n) | O(n)


  • 19
    V

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

  • 5
    F

    Exactly same to your idea.
    Here's java version.

        public int repeatedStringMatch(String A, String B) {
            int i = 0, j = 0;
            while (i < A.length()) {
                j = 0;
                while (j < B.length() && A.charAt((i + j) % A.length()) == B.charAt(j)) {
                    j++;
                }
                if (j == B.length()) {
                    return (i + j) / A.length() + ((i + j) % A.length() == 0 ? 0 : 1);
                }
                i++;
            }
            return -1;
        }
    

  • 1
    K

    Interesting.. I like that you don't need to use extra memory. Wondering if there is a way to use KMP with your solution to reduce Big O.


  • 0
    V

    @k_j good idea, thanks. I've added KMP solution and description.


  • 0
    Y
    This post is deleted!

  • 0
    X

    @votrubac Why we can safely i += j + 1, even though i + j in the inner loop is larger than a.size() - 1?


  • 0
    V

    @xpfxzxc This is because we never do a[i], we do a[i % a.size()] instead. i % a.size() can only be [0, a.size() - 1], so it's save. This technique allows looping through the string without copying it several times.


  • 2
    X

    @votrubac My English is not good. Sorry for your misunderstanding. (And I couldn't come up with a test case serveral days ago.)
    I found your KMP solution miss a corner case. Here is my test case I came up with just now.
    Input: "acxabab"
    "abac"
    Your answer: -1
    Expected answer: 2

    Just becauce i += j + 1
    @awice


  • 0
    V

    @xpfxzxc thanks for finding a missing OJ test case. I was aiming to optimize for the performance, and OJ accepted my solution. In KMP, it should be ++i instead of i += j + 1. I've updated my solution.


  • 7

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

  • 0
    V

    @mylzsd indeed, it's a smarter way to increase i :) I had something like that in mind, but originally derailed by the missing OJ case (it accepted "i += j +1"). I've updated my solution based on your observation; also, I made the prefix table 1-based to avoid multiple "-1" checks.


  • 1
    X

    @votrubac if (b[pp - 1] == b[sp - 1]) ++pp;
    The initial value of pp is 0, then p-1 is -1, which means that it will cause Runtime Error.


  • 0
    V

    @xpfxzxc thanks for checking, I copied the code from the wrong window... updated with the correct one.


  • 0
    6

    Could you please explain whyi += j - prefTable[j - 1] ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.