get a list of duplicated substrings in the string

Question

There is a javascript string var source;

What's the easiest way to find all DUPLICATED substrings of length let's say 20 (it is OK, if they are crossed, it is OK, if even substrings of 21 are met, they will be repeated in the answer twice from 0 to 20 and from 1 to 21).

The easiest way is to use

var len=20;
var sourceLen=source.length;
for (var i=0; i<sourceLen; i++){
    for (var j=i+1; j<sourceLen; j++){
        if (source.substring(i,i+len)==source.substring(j,j+len)){
            console.log(source.substring(i,i+len));
        }
    }
}

But you can see if the string grows, the calculation time grows even more. I was thinking about switching the value by steps (j+=5; instead of j++), but there are issues.

Also I was thinking about using .indexOf to get the same results with just one for-loop.

Are there any smarter way to get a list of duplicated strings of length 20 in the string?

Answer 1

Also I was thinking about using .indexOf to get the same results with just one for-loop.

indexOf still does loop the string internally. Sure, we don't know whether they have implemented a more efficient string search algorithm; it might be worth a try.

Are there any smarter way to get a list of duplicated strings of length 20 in the string?

Use a set of all substrings that has a quick lookup time.

function dupls(source, len, callback) {
    var subsSet = {};
    for (var i=0, l=source.length-len; i<l; i++) {
        var sub = source.slice(i, len);
        if (sub in subsSet) // or, possibly better, subsSet[sub]===true
            callback(sub);
        else
            subsSet[sub] = true;
    }
}
dupls("…", 20, console.log.bind(console));