最近こんな質問をされました。これが私が[最終的に]思いついた解決策です。JavaScript でやったのは、その言語では非常に簡単だからです。
基本的な概念は、可能な限り最小の複数文字の回文 (2 文字または 3 文字のいずれか) を探して文字列をたどることです。それができたら、回文でなくなるまで両側の境界線を広げます。その長さが現在の最長のものより長い場合は、保管して移動します。
// 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;
}
これは間違いなくクリーンアップされ、もう少し最適化される可能性がありますが、最悪のシナリオ (同じ文字の文字列) を除いて、かなり良いパフォーマンスが得られるはずです。