note
fizbin
Given the number who have gone before, surely this has been done already, but...
<p>
<table><tr class="code"><td bgcolor="#000000" color="#000000">
<pre><font size="-1" color="#000000">
sub fizbin {
return $_[0] unless ($_[0] and length($_[0]) > 1);
my @string = (300, unpack("U*", $_[0]), 301);
my $palstart, $palend;
my ($bestlen, $beststart, $bestend) = (-1,-1,-1);
for ($palmid = 1; $palmid < $#string; $palmid++)
{
if ($string[$palmid] == $string[$palmid+1])
{ # try even-length palindrome
($palstart, $palend) = ($palmid, $palmid+1);
while ($string[$palend+1] == $string[$palstart-1])
{
$palend++; $palstart--;
}
if ($bestlen < $palend - $palstart)
{
($bestlen, $bestend, $beststart) =
($palend - $palstart, $palend, $palstart);
}
}
# try odd-length palindrome
($palstart, $palend) = ($palmid, $palmid);
while ($string[$palend+1] == $string[$palstart-1])
{
$palend++; $palstart--;
}
if ($bestlen < $palend - $palstart)
{
($bestlen, $bestend, $beststart) =
($palend - $palstart, $palend, $palstart);
}
}
pack("U*", @string[$beststart..$bestend]);
}
</font></pre>
</td></tr></table>
It's also unfortunately an O(n^2) algorithm, but my initial O(n) idea turned out to be badly flawed. (Actually, I guess it's O(n*m), where "n" is the length of the input and "m" is the length of the longest palindrome - in the worst case, a string of all the same letter, it'd be O(n^2))
<p>
Note that it'll also work on unicode strings, assuming that perl knows that its argument is a unicode string.
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-246930">
<code>--
@/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/;
map{y/X_/\n /;print}map{pop@$_}@/for@/</code>
</div></div>
382567
382567