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