Longest palindromic substrings
Let given a string s. The goal is to find the longest palindromic substring in s.
Julia
<lang julia>function allpalindromics(s)
list, len = String[], length(s)
for i in 1:len-1, j in i+1:len
substr = s[i:j]
if substr == reverse(substr)
push!(list, substr)
end
end
return list
end
for teststring in ["babaccd", "rotator", "reverse", "forever", "several", "palindrome"]
list = sort!(allpalindromics(teststring), lt = (x, y) -> length(x) < length(y))
println(isempty(list) ? "No palindromes of 2 or more letters found in \"$teststring." :
"The longest palindromic substring of $teststring is: \"",
join(list[findall(x -> length(x) == length(list[end]), list)], "\" or \""), "\"")
end
</lang>
- Output:
The longest palindromic substring of babaccd is: "bab" or "aba" The longest palindromic substring of rotator is: "rotator" The longest palindromic substring of reverse is: "rever" The longest palindromic substring of forever is: "rever" The longest palindromic substring of several is: "eve" No palindromes of 2 or more letters found in "palindrome."
Phix
<lang Phix>function longest_palindromes(string s) -- s = lower/strip_spaces_and_punctuation/utf8_to_utf32, if rqd
integer longest = 2 -- (do not treat length 1 as palindromic)
-- integer longest = 1 -- (do not treat length 0 as palindromic) [works just fine too]
sequence res = {}
for i=1 to length(s) do
for e=length(s) to i+longest-1 by -1 do
if s[e]=s[i] then
string p = s[i..e]
integer lp = length(p)
if lp>=longest and p=reverse(p) then
if lp>longest then
longest = lp
res = {p}
elsif not find(p,res) then -- (or just "else")
res = append(res,p)
end if
end if
end if
end for
end for
return res -- (or "sort(res)" or "unique(res)", as needed)
end function
constant tests = {"babaccd","rotator","reverse","forever","several","palindrome","abaracadaraba"} for i=1 to length(tests) do
printf(1,"%s: %v\n",{tests[i],longest_palindromes(tests[i])})
end for</lang>
- Output:
babaccd: {"bab","aba"}
rotator: {"rotator"}
reverse: {"rever"}
forever: {"rever"}
several: {"eve"}
palindrome: {}
abaracadaraba: {"aba","ara","aca","ada"}
with longest initialised to 1, you get the same except for palindrome: {"p","a","l","i","n","d","r","o","m","e"}
faster
<lang Phix>function Manacher(string text)
-- Manacher's algorithm (linear time) -- based on https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-4 -- but with a few tweaks, renames, and bugfixes (in particular the < (positions-1), which I later found LIJIE already said) sequence res = {} integer positions = length(text)*2+1 if positions>1 then sequence LPS = repeat(0,positions) LPS[2] = 1 integer centerPosition = 1, centerRightPosition = 2, maxLPSLength = 0 for currentRightPosition=2 to positions-1 do integer lcp = LPS[currentRightPosition+1], diff = centerRightPosition - currentRightPosition -- If currentRightPosition is within centerRightPosition if diff >= 0 then -- get currentLeftPosition iMirror for currentRightPosition integer iMirror = 2*centerPosition-currentRightPosition + 1 lcp = min(LPS[iMirror], diff) end if -- Attempt to expand palindrome centered at currentRightPosition -- Here for odd positions, we compare characters and -- if match then increment LPS Length by ONE -- If even position, we just increment LPS by ONE without -- any character comparison while ((currentRightPosition + lcp) < (positions-1) and (currentRightPosition - lcp) > 0) and ((remainder(currentRightPosition+lcp+1, 2) == 0) or (text[floor((currentRightPosition+lcp+1)/2)+1] == text[floor((currentRightPosition-lcp-1)/2)+1] )) do lcp += 1 end while LPS[currentRightPosition+1] = lcp maxLPSLength = max(lcp,maxLPSLength) // If palindrome centered at currentRightPosition // expand beyond centerRightPosition, // adjust centerPosition based on expanded palindrome. if (currentRightPosition + lcp) > centerRightPosition then centerPosition = currentRightPosition centerRightPosition = currentRightPosition + lcp end if end for for p=1 to positions do if LPS[p] = maxLPSLength then integer start = floor((p-1 - maxLPSLength)/2) + 1, finish = start + maxLPSLength - 1 string r = text[start..finish] if not find(r,res) then res = append(res,r) end if end if end for end if return res
end function
include mpfr.e mpfr pi = mpfr_init(0,-10001) -- (set precision to 10,000 dp, plus the "3.") mpfr_const_pi(pi) string piStr = mpfr_sprintf("%.10000Rf", pi),
s = shorten(piStr)
printf(1,"%s: %v\n",{s,Manacher(piStr)})</lang>
- Output:
(Same as above if given the same inputs.)
However, while Manacher finishes 10,000 digits in 0s, longest_palindromes takes 1s for 2,000 digits, 15s for 5,000 digits, and 2 mins for 10,000 digits,
which goes to prove that longest_palindromes() above is O(n2), whereas Manacher() is O(n).
3.141592653589793238...05600101655256375679 (10,002 digits): {"398989893","020141020"}
Raku
This version regularizes (ignores) case and ignores non alphabetic characters. It is only concerned with finding the longest palindromic substrings so does not exhaustively find all possible palindromes. If a palindromic substring is found to be part of a longer palindrome, it is not captured separately.
<lang perl6>my @chars = q:to/END/ .lc.comb: /\w/;
Lyrics to "Bob" copyright Weird Al Yankovic https://www.youtube.com/watch?v=JUQDzj6R3p4
I, man, am regal - a German am I Never odd or even If I had a hi-fi Madam, I'm Adam Too hot to hoot No lemons, no melon Too bad I hid a boot Lisa Bonet ate no basil Warsaw was raw Was it a car or a cat I saw?
Rise to vote, sir Do geese see God? "Do nine men interpret?" "Nine men," I nod Rats live on no evil star Won't lovers revolt now? Race fast, safe car Pa's a sap Ma is as selfless as I am May a moody baby doom a yam?
Ah, Satan sees Natasha No devil lived on Lonely Tylenol Not a banana baton No "x" in "Nixon" O, stone, be not so O Geronimo, no minor ego "Naomi," I moan "A Toyota's a Toyota" A dog, a panic in a pagoda
Oh no! Don Ho! Nurse, I spy gypsies - run! Senile felines Now I see bees I won UFO tofu We panic in a pew Oozy rat in a sanitary zoo God! A red nugget! A fat egg under a dog! Go hang a salami, I'm a lasagna hog! END
- "
my @cpfoa;
for ^@chars -> $i {
my ($rev,$fwd) = 0, 0;
++$rev if $i and @chars[$i - 1] eq @chars[$i];
loop {
quietly last if $rev > $i or $rev and @chars[$i - $rev] ne @chars[$i + $fwd];
++$rev;
++$fwd;
}
@cpfoa[(my $pal = @chars[$i - $rev ^..^ $i + $fwd].join).chars].push: $pal if $rev + $fwd > 2;
}
.unique.sort.put for @cpfoa.grep( *.so ).tail;</lang>
- Output:
doninemeninterpretninemeninod godarednuggetafateggunderadog
REXX
<lang rexx>/*REXX program finds and displays the longest palindromic string(s) in a given string. */ parse arg s /*obtain optional argument from the CL.*/ if s== | s=="," then s= 'babaccd rotator reverse forever several palindrome abaracadaraba'
do i=1 for words(s); x= word(s, i) /*obtain a string to be examined. */
L= length(x) /*obtain length of the specified string*/
longest= 0 /*longest palindrome found (so far). */
@.= /*initialize all possible lists to null*/
do j=1 for L /*search for palindroms in the string S*/
do k=j to L; LL= k - j + 1 /*obtain length of possible palindroms.*/
if LL<longest then iterate /*Palindrome length<max? Then skip it.*/
$= substr(x, j, LL) /*obtain a possible palindromic substr.*/
if $\==reverse($) then iterate /*Not a palindrome? Then skip it.*/
longest= max(longest, LL) /*set the longest palindrome to this L.*/
@.LL= @.LL $ /*add a palindromic substring to a list*/
end /*k*/
end /*j*/
say
say ' longest palindromic substrings for string: ' x
say '────────────────────────────────────────────'copies('─', 2+length(x))
do n=1 for words(@.longest) /*show longest palindromic substrings. */
say ' (length='longest") " word(@.longest, n)
end /*n*/
end /*i*/ /*stick a fork in it, we're all done. */</lang>
- output when using the default input:
longest palindromic substrings for string: babaccd
─────────────────────────────────────────────────────
(length=3) bab
(length=3) aba
longest palindromic substrings for string: rotator
─────────────────────────────────────────────────────
(length=7) rotator
longest palindromic substrings for string: reverse
─────────────────────────────────────────────────────
(length=5) rever
longest palindromic substrings for string: forever
─────────────────────────────────────────────────────
(length=5) rever
longest palindromic substrings for string: several
─────────────────────────────────────────────────────
(length=3) eve
longest palindromic substrings for string: palindrome
────────────────────────────────────────────────────────
(length=1) p
(length=1) a
(length=1) l
(length=1) i
(length=1) n
(length=1) d
(length=1) r
(length=1) o
(length=1) m
(length=1) e
longest palindromic substrings for string: abaracadaraba
───────────────────────────────────────────────────────────
(length=3) aba
(length=3) ara
(length=3) aca
(length=3) ada
(length=3) ara
(length=3) aba
Ring
<lang ring> load "stdlib.ring"
st = "babaccd" palList = []
for n = 1 to len(st)-1
for m = n+1 to len(st)
sub = substr(st,n,m-n)
if ispalindrome(sub) and len(sub) > 1
add(palList,[sub,len(sub)])
ok
next
next
palList = sort(palList,2) palList = reverse(palList) resList = [] add(resList,palList[1][1])
for n = 2 to len(palList)
if palList[1][2] = palList[n][2]
add(resList,palList[n][1])
ok
next
see "Input: " + st + nl see "Longest palindromic substrings:" + nl see resList </lang>
- Output:
Input: babaccd Longest palindromic substrings: bab aba