Longest palindromic substrings: Difference between revisions
Added Algol 68
Alpha bravo (talk | contribs) |
(Added Algol 68) |
||
Line 45:
'drome' -> 'e'
'the abbatial palace' -> 'abba'
</pre>
=={{header|ALGOL 68}}==
Palindromes of length 1 or more are detected, finds the left most palindrome if there are several of the same length.<br>
Treats upper and lower case as distinct and does not require the characters to be letters.
<lang algol68>BEGIN # find the longest palindromic substring of a string #
# returns the length of s #
OP LENGTH = ( STRING s )INT: ( UPB s + 1 ) - LWB s;
# returns s right-padded with blanks to at least w characters or s if it is already wide enough #
PRIO PAD = 1;
OP PAD = ( STRING s, INT w )STRING:
BEGIN
STRING result := s;
WHILE LENGTH result < w DO result +:= " " OD;
result
END # PAD # ;
# returns the longest palindromic substring of s #
# if there are multiple substrings with the longest length, the leftmost is returned #
PROC longest palindromic substring = ( STRING s )STRING:
IF INT len = LENGTH s;
len < 2
THEN s
ELSE
INT lwb s = LWB s;
INT upb s = UPB s;
STRING result := s[ lwb s ];
IF s[ lwb s + 1 ] = s[ lwb s ] THEN
# the first two characters are a palindrome #
result +:= s[ lwb s + 1 ]
FI;
FOR i FROM lwb s + 1 TO upb s - 1 DO
INT p start := i;
INT p end := i + 1;
BOOL have palindrome := FALSE;
IF s[ i - 1 ] = s[ i + 1 ] THEN
# odd length palindrome at i - 1 #
p start := i - 1;
have palindrome := TRUE
ELIF s[ i ] = s[ i + 1 ] THEN
# even length palindrome at i #
have palindrome := TRUE
FI;
IF have palindrome THEN
# have a palindrome at p start : p end #
# attempt to enlarge the range #
WHILE IF p start = lwb s OR p end = upb s
THEN FALSE
ELSE s[ p start - 1 ] = s[ p end + 1 ]
FI
DO
# can extend he palindrome #
p start -:= 1;
p end +:= 1
OD;
IF STRING new palindrome = s[ p start : p end ];
LENGTH new palindrome > LENGTH result
THEN
# have a longer palindrome #
result := new palindrome
FI
FI
OD;
result
FI # longest palindromic substring # ;
# finds the longest palindromic substring of s and checks it is the expacted value #
PROC test = ( STRING s, expected value )VOID:
BEGIN
STRING palindrome = longest palindromic substring( s );
print( ( ( """" + s + """" ) PAD 38, " -> ", ( """" + palindrome + """" ) PAD 36
, IF palindrome = expected value THEN "" ELSE " NOT " + expected value + " ???" FI
, newline
)
)
END # test longest palindromic substring # ;
test( "three old rotators", "rotator" );
test( "never reverse", "ever reve" );
test( "stable was I ere I saw elbatrosses", "table was I ere I saw elbat" );
test( "abracadabra", "aca" );
test( "drome", "d" );
test( "x", "x" );
test( "the abbatial palace", "abba" );
test( "", "" );
test( "abcc", "cc" );
test( "abbccc", "ccc" )
END</lang>
{{out}}
<pre>
"three old rotators" -> "rotator"
"never reverse" -> "ever reve"
"stable was I ere I saw elbatrosses" -> "table was I ere I saw elbat"
"abracadabra" -> "aca"
"drome" -> "d"
"x" -> "x"
"the abbatial palace" -> "abba"
"" -> ""
"abcc" -> "cc"
"abbccc" -> "ccc"
</pre>
| |||