Longest palindromic substrings: Difference between revisions

 

=={{header|11l}}==

V t = Array(‘^’s‘$’).join(‘#’)

V n = t.len

‘drome’,

‘the abbatial palace’]

 

{{out}}

'drome' -> 'e'

'the abbatial palace' -> 'abba'

</pre>

 

=={{header|F_Sharp|F#}}==

===Manacher Function===

// Manacher Function. Nigel Galloway: October 1st., 2020

let Manacher(s:string) = let oddP,evenP=Array.zeroCreate s.Length,Array.zeroCreate s.Length

match (Ʃ+evenP.[Ʃ])>g with true->fGe (Ʃ-evenP.[Ʃ]+1) (Ʃ+evenP.[Ʃ]) (Ʃ+1) |_->fGe n g (Ʃ+1)

(fGo 0 -1 0,fGe 0 -1 0)

 

===The Task===

let fN g=if g=[||] then (0,0) else g|>Array.mapi(fun n g->(n,g))|>Array.maxBy snd

let lpss s=let n,g=Manacher s in let n,g=fN n,fN g in if (snd n)*2+1>(snd g)*2 then s.[(fst n)-(snd n)..(fst n)+(snd n)] else s.[(fst g)-(snd g)+1..(fst g)+(snd g)]

let test = ["three old rotators"; "never reverse"; "stable was I ere I saw elbatrosses"; "abracadabra"; "drome"; "the abbatial palace"; ""]

test|>List.iter(fun n->printfn "A longest palindromic substring of \"%s\" is \"%s\"" n (lpss n))

{{out}}

<pre>

A longest palindromic substring of "" is ""

</pre>

 

=={{header|Go}}==

{{trans|Wren}}

 

import (

fmt.Printf(" %-13s Length %d -> %v\n", s, len(longest[0]), longest)

}

 

{{out}}

A list version, written out of curiosity. A faster approach could be made with an indexed datatype.

 

 

longestPalindromes :: String -> ([String], Int)

where

rjust n c = drop . length <*> (replicate n c ++)

{{Out}}

<pre>Longest palindromic substrings:

"the abbatial palace" -> (["abba"],4)

"" -> ([],0)</pre>

 

=={{header|Julia}}==

list, len = String[], length(s)

for i in 1:len-1, j in i+1:len

join(list[findall(x -> length(x) == length(list[end]), list)], "\" or \""), "\"")

end

<pre>

The longest palindromic substring of babaccd is: "bab" or "aba"

 

===Manacher algorithm===

function manacher(str)

s = "^" * join(split(str, ""), "#") * "\$"

"The longest palindromic substring of $teststring is: \"$pal\"")

end

<pre>

The longest palindromic substring of babaccd is: "aba"

No palindromes of 2 or more letters found in "palindrome."

The longest palindromic substring of abaracadabra is: "ara"

</pre>

 

=={{header|Perl}}==

The short one - find all palindromes with one regex.

use warnings;

 

pop =~ /(.+) .? (??{reverse $1}) (?{ $best[length $&]{$&}++ }) (*FAIL)/x;

keys %{pop @best};

{{out}}

<pre>

Longest Palindrome For abaracadabra = aba ara aca ada

</pre>

 

use warnings;

 

#@ARGV = 'pi.dat'; # uncomment to use this file or add filename to command line

my $right = substr $forward, $i, $range;

my $left = substr $backward, $length - $i, $range;

($len = 2 * length $&) >= $#best and

$best[ $len ]{substr $forward, $i - length $&, $len}++;

($len = 1 + 2 * length $1) >= $#best and

$best[ $len ]{substr $forward, $i - length $1, $len}++;

I, man, am regal - a German am I

toot

{{out}}

<pre>

 

=={{header|Phix}}==

{{out}}

<pre>

palindrome: {}

abaracadaraba: {"aba","ara","aca","ada"}

</pre>

with longest initialised to 1, you get the same except for <code>palindrome: {"p","a","l","i","n","d","r","o","m","e"}</code>

 

=={{header|Python}}==

(This version ignores case but allows non-alphanumerics).

 

 

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Longest palindromic substrings:

This version regularizes (ignores) case and ignores non alphanumeric 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. Showing the longest 5 palindromic substring groups. Run it with no parameters to operate on the default; pass in a file name to run it against that instead.

 

Lyrics to "Bob" copyright Weird Al Yankovic

https://www.youtube.com/watch?v=JUQDzj6R3p4

}

 

{{out}}

Returns the length, (the count) and the list:

 

=={{header|REXX}}==

parse arg s /*obtain optional argument from the CL.*/

if s==''|s=="," then s='babaccd rotator reverse forever several palindrome abaracadaraba'

@= @ $ /*add a palindromic substring to a list*/

if short then return 1 /*we have found one palindrome. */

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ring}}==

load "stdlib.ring"

 

see "Longest palindromic substrings:" + nl

see resList

{{out}}

<pre>

 

The Phix entry examples have been used.

 

var longestPalSubstring = Fn.new { |s|

var longest = Lst.distinct(longestPalSubstring.call(s))

Fmt.print(" $-13s Length $d -> $n", s, longest[0].count, longest)

 

{{out}}