Sunday, May 29, 2022
HomeWordPress DevelopmentDiscover all substring of a given string in O(n^2) time.

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


Under is the programmer written in JavaScript to search out the all attainable substrings of a given string in O(N^2) time complexity and an additional O(1) house;



Programme

operate genSubstrings(inputString){
    debugger;
    let resultArray = [];
    // outer loop to run n occasions [n = size of string]
    for(let i = 0; i < inputString.size; i++){
        // pushing first char of string as substring
        // as we all know that every char might be substring itself too.
        resultArray.push(inputString[i]);
        // inside loop to run n - 1 occasions;
        for(let j = i + 1; j < inputString.size; j++){
            // get final substring and append the brand new subsequent char
            resultArray.push(
              resultArray[resultArray.length - 1] + inputString[j]
            );
        }
    }

    return resultArray;
}
Enter fullscreen mode

Exit fullscreen mode



Output

genSubstrings("abcd");

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

Exit fullscreen mode

 
I searched web for a greater answer which may run in much less then O(N^2) time complexity however did not discover any.

If anybody has a greater answer please write in feedback, It is going to be actually useful.
 

The thumbnail is taken from geekforgeek

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments