@givemoneybiatch
Немного веб, немного гейм

Реален ли поиск палиндромов в огромном тексте на js в браузере?

Есть требование реализовать поиск слов-палиндромов ("madam") и палиндромов-предложений ("tree leaves leaves tree") в сколь угодно большом тексте, который вводит пользователь. Текст может быть хоть вся "война и мир", хоть вся британская энциклопедия. И в этом тексте необходимо найти самые длинные n палиндромов.
Например, палиндромом может быть текст, который содержит 74,633 букв и его скрипт тоже должен определять.
Ниже прикрепляю то, что примерно получилось у меня для поиска палиндромов-слов(для поиска палиндромов-предложений отличается совсем немного), но сложность алгоритма O(n^2) и он виснет уже при 500 буквах (500*500 = 199809 итераций).
Даже если предположить, что сложность алгоритма O(n), то будет виснуть при 200к буквах, что явно меньше чем содержание "войны и мир".
Насколько адекватно такое требовать реализовать на джс? И насколько это осуществимо?

let lookFor = (arr) => {
        const length = arr.length;
        let resultSet = new Set();

        for (let i = 0; i < length; i++) {
            for (let j = 0; j < length; j++) {
                let subArr = arr.slice(i, j + 1);
                if (isPalindrome(subArr)) {
                    let palindromeStr = stripSpecial(subArr.join(' '));
                    resultSet.add(palindromeStr);
                }
            }
        }
        return resultSet;
    }

let isPalindrome = (subArr) => {
        // remove all special characters
        let re = /[\`\~\!\@\#\$\%\^\:\;\&\?\*\(\)\_\-\=\+\,\[\]\|\/\'\"\.]/g;
        let str = subArr.join(' ').toLowerCase().replace(re, '');
        str = str.replace(/ /g, '');
        var len = str.length;
        for (var i = 0; i < len / 2; i++) {
                // as long as the characters from each part match, the FOR loop will go on
                if (str[i] !== str[len - 1 - i]) {
                    return false;
                }
        }
        // both parts are strictly equal, it returns true => The string is a palindrome
        return true;
}
  • Вопрос задан
  • 525 просмотров
Пригласить эксперта
Ответы на вопрос 3
@strelok011
Теоретически - можно осуществить. В лоб - не получится. Нужно применять инженерные решения для bigdata, оптимизации, возможно кластеризацию задачи и проч. Т.е. разом разобрать этот объем не получится. Не хватит памяти и производительности.
Ответ написан
Комментировать
@SpaceX_1
junior front-end developer
isPalindrome = (string) => {
  string = string.toLocaleLowerCase();
  return Array.from(string).toString() === Array.from(string).reverse().toString()
}

Это код для isPalindrome. У вас слишком большая цикломатическая сложность, избегайте такого к-ва вложенностей.
Ответ написан
Комментировать
ThunderCat
@ThunderCat Куратор тега JavaScript
{PHP, MySql, HTML, JS, CSS} developer
пару замечаний:
// remove all special characters - вероятно сделать 1 раз для всего текста будет эффективнее чем дергать каждый раз в цикле.

function reverseString(str) {
    return str.split("").reverse().join("");
}
скорее всего (не факт) будет работать быстрее развернуть всю строку и проверить на равенство.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы