The Repeated String Match Algorithm in Javascript

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”).

The length of A and B will be between 1 and 10000.

NodeJs / Javascript

The most intuitive way is to concatenate A until the length is bigger than the string B – as it will not match B concatenating more A’s.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/**
 * @param {string} A
 * @param {string} B
 * @return {number}
 */
var repeatedStringMatch = function(A, B) {
    var c = "";
    for (var i = 0; i < B.length/A.length + 1; ++ i) {
        c += A;
        if (c.includes(B)) {
            return i + 1;
        }
    }
    return -1;
};

/**
 * @param {string} A
 * @param {string} B
 * @return {number}
 */
var repeatedStringMatch = function(A, B) {
    var c = "";
    for (var i = 0; i < B.length/A.length + 1; ++ i) {
        c += A;
        if (c.includes(B)) {
            return i + 1;
        }
    }
    return -1;
};

We use the Javascript‘s String.prototype.includes() method to check if a string has included another substring. As this algorithm is not trivial e.g. KMP to check if a string is substring of another, we want to reduce the number of substring checks.

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * @param {string} A
 * @param {string} B
 * @return {number}
 */
var repeatedStringMatch = function(A, B) {
    var c = "";
    var q = 0;
    for (; c.length < B.length; q ++) c += A;
    if (c.includes(B)) return q;
    if ((c + A).includes(B)) return q + 1;
    return -1;
};

/**
 * @param {string} A
 * @param {string} B
 * @return {number}
 */
var repeatedStringMatch = function(A, B) {
    var c = "";
    var q = 0;
    for (; c.length < B.length; q ++) c += A;
    if (c.includes(B)) return q;
    if ((c + A).includes(B)) return q + 1;
    return -1;
};

The above is the optimised version for the string match algorithm. For a string to be able to include another substring, it has to be more lengthy than another, therefore, we concatenate the string until the length is more than the target string. Then we perform one String.prototype.include check, if it is not successful, we concatenate one more time and perform another check.

This algorithm requires at most two calls to String.prototype.include() method. And it requires O(B/A) complexity to perform the string concatenation.

–EOF (The Ultimate Computing & Technology Blog) —