Find all substring of a given string in O(n^2) time.

Below is the programmer written in JavaScript to find the all possible substrings of a given string in O(N^2) time complexity and an extra O(1) space;

Programme

function genSubstrings(inputString){
    debugger;
    let resultArray = [];
    // outer loop to run n times [n = size of string]
    for(let i = 0; i < inputString.length; i++){
        // pushing first char of string as substring
        // as we know that each char will be substring itself too.
        resultArray.push(inputString[i]);
        // inner loop to run n - 1 times;
        for(let j = i + 1; j < inputString.length; j++){
            // get last substring and append the new next char
            resultArray.push(
              resultArray[resultArray.length - 1] + inputString[j]
            );
        }
    }

    return resultArray;
}

Output

genSubstrings("abcd");

(10) ['a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd']

 
I searched internet for a better solution which can run in less then O(N^2) time complexity but didn't find any.

If anyone has a better solution please write in comments, It will be really helpful.
 

The thumbnail is taken from geekforgeek

Comments

[Randall]

For any given string of length n, the number of substrings is n(n + 1) / 2.

This implies an algorithm with better than O(n^2) complexity is not possible, since at a minimum you have to insert all of those n(n + 1) / 2 substrings into an array.

[Rajesh Royal]

What if we need to print those substrings.
Do you have any code snippet of doing it.

[Normal GU-I]

Well, I don't think there is a better way to do this except with O(N^2); But this can be helpful - Wikipedia suffix tree