BUU,
SHAME ON YOU!
When you mentioned in #perl last night that you intended to make a SoPW post about this, I assumed you would have also mentioned that it was for a job application. I haven't had a chance to refine my non-regex solution on my scratch pad, but here it is for the record.
#!/usr/bin/perl
use strict;
use warnings;
print longest_palindrome( 'sacascascsacascascascadvgkgjsflfjgfk' );
sub longest_palindrome {
my %lookup;
my ($index, $record) = (-1, 0);
push @{ $lookup{ substr($_[0], $_, 1) } } , $_ for 0 .. (length $_
+[0]) - 1;
for my $letter ( keys %lookup ) {
my $last = $#{ $lookup{ $letter } };
for my $start ( 0 .. $last - 1 ) {
for my $end ( reverse ( $start + 1 .. $last ) ) {
my $pos = $lookup{ $letter }[ $start ];
my $length = $lookup{ $letter }[ $end ] - $pos + 1;
if ( $length > $record ) {
my $palindrome = substr($_[0], $pos, $length);
if ( $palindrome eq reverse $palindrome ) {
($index, $record) = ($pos, $length);
last;
}
}
}
}
}
return substr($_[0], $index, $record);
}
|
Update: While I do not know if you intended to use any of the responses to your advantage in applying for the job, I do know you got the problem from the ad as you gave me the link in IRC. Additionally, you indicated you intended to apply for the job. Shame on me for not wording my admonishment better.
Update 2: Corrected another logic flaw pointed out by ccn, which makes it even slower :-(
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|
