Найдите все подстроки заданной строки за время O(n^2).

Ниже приведена программа на JavaScript для нахождения всех возможных подстрок заданной строки за время O(N^2) и дополнительное пространство O(1);

Программа

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;
}
Вход в полноэкранный режим Выход из полноэкранного режима

Вывести

genSubstrings("abcd");

(10) ['a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd']
Войти в полноэкранный режим Выход из полноэкранного режима

 
Я искал в интернете лучшее решение, которое может выполняться за время менее O(N^2), но не нашел.

Если у кого-то есть лучшее решение, пожалуйста, напишите в комментариях, это будет очень полезно.
 

Иллюстрация взята с сайта geekforgeek

Оцените статью
Procodings.ru
Добавить комментарий