Longest palindromic substrings: Difference between revisions

 

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

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

V n = t.len

‘drome’,

‘the abbatial palace’]

 

{{out}}

 

=={{header|Action!}}==

BYTE l,r

 

Test("qwertyuiop")

Test("")

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_palindromic_substrings.png Screenshot from Atari 8-bit computer]

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.

# returns the length of s #

OP LENGTH = ( STRING s )INT: ( UPB s + 1 ) - LWB s;

test( "abcc", "cc" );

test( "abbccc", "ccc" )

{{out}}

<pre>

=={{header|Arturo}}==

{{trans|Nim}}

 

lps: function [s][

print [str "->" (0 < size palindromes)? -> join.with:", " palindromes

-> "X"]

 

{{out}}

 

=={{header|AutoHotkey}}==

found := [], result := [], maxL := 0

while (StrLen(str) >= 2 && StrLen(str) >= maxL){

output := v output

return output

(

three old rotators

}

MsgBox % output

{{out}}

<pre>three old rotators > ["rotator"]

=={{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>

=={{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:

{{works with|jq}}

'''Works with gojq, the Go implementation of jq'''

length as $len

| if $len <= 1 then .

| longestPalindromicSubstring as $longest

| " \(.): length \($longest[0]|length) -> \($longest)"

 

{{out}}

 

=={{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"

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

ExpandSubsequenceTry[seq_List, beginpos : {a_, b_}] :=

Module[{len, maxbroaden, last},

StringJoin@LongestPalindromicSubsequence[Characters["abracadabra"]]

StringJoin@LongestPalindromicSubsequence[Characters["drome"]]

{{out}}

<pre>"rotator"

=={{header|Nim}}==

Simple algorithm but working on Unicode code points.

 

func isPalindrome(s: seq[Rune]): bool =

echo str, " → ", "<no palindromic substring of two of more letters found>"

else:

 

{{out}}

=={{header|Perl}}==

The short one - find all palindromes with one regex.

 

use strict; # https://rosettacode.org/wiki/Longest_palindromic_substrings

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

keys %{pop @best};

{{out}}

<pre>

</pre>

The faster one - does the million digits of Pi in under half a second.

 

use strict; # https://rosettacode.org/wiki/Longest_palindromic_substrings

I, man, am regal - a German am I

toot

{{out}}

<pre>

=={{header|Phix}}==

{{trans|Raku}}

<span style="color: #000080;font-style:italic;">-- demo/rosetta/Longest_palindromic_substrings.exw (plus two older versions)</span>

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">longest_palindromes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

(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.

import "/fmt" for Fmt

 

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

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

 

{{out}}