например, "ccddcc" в строке "abaccddccefe"
Я думал о решении, но оно выполняет в O (n^2) время
Алгоритм 1:
Шаги: это - метод грубой силы
Проблемы: 1. Этот алгоритм выполняет в O (n^2) время.
Алгоритм 2:
Можете Вы парни думать об алгоритме, который работает в лучшее время. Если возможно O (n) время
Недавно мне задали этот вопрос. Вот решение, которое я [в конце концов] придумал. Я сделал это на JavaScript, потому что это довольно просто на этом языке.
Основная концепция заключается в том, что вы просматриваете строку в поисках наименьшего возможного многосимвольного палиндрома (двух- или трехсимвольного). Получив его, расширяйте границы с обеих сторон до тех пор, пока он не перестанет быть палиндромом. Если эта длина больше, чем текущая самая длинная, сохраните ее и двигайтесь дальше.
// This does the expanding bit.
function getsize(s, start, end) {
var count = 0, i, j;
for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
if (s[i] !== s[j]) {
return count;
}
count = j - i + 1; // keeps track of how big the palindrome is
}
return count;
}
function getBiggestPalindrome(s) {
// test for simple cases
if (s === null || s === '') { return 0; }
if (s.length === 1) { return 1; }
var longest = 1;
for (var i = 0; i < s.length - 1; i++) {
var c = s[i]; // the current letter
var l; // length of the palindrome
if (s[i] === s[i+1]) { // this is a 2 letter palindrome
l = getsize(s, i, i+1);
}
if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
l = getsize(s, i+1, i+1);
}
if (l > longest) { longest = l; }
}
return longest;
}
Это определенно может быть очищено и оптимизировано немного больше, но это должно иметь довольно хорошую производительность во всех случаях, кроме худшего сценария (строка из одной и той же буквы).