Есть требование реализовать поиск слов-палиндромов ("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;
}
