Finding "sub-palindromes".

Question

The shortest code that finds all unique "sub-palindromes" of a string, that is: any substring with length > 1 that is a palindrome.

eg.1

input: "12131331"
output: "33", "121", "131", "313", "1331"

eg.2

input: "3333"
output: "33", "333", "3333"

Answer 1

J, 24 31 40

~.(#~(1<#*]-:|.)&>),<\\.

Sample use:

   ~.(#~(1<#*]-:|.)&>),<\\. '12131331'
┌───┬───┬───┬────┬──┐
│121│131│313│1331│33│
└───┴───┴───┴────┴──┘
   ~.(#~(1<#*]-:|.)&>),<\\. '3333'
┌──┬───┬────┐
│33│333│3333│
└──┴───┴────┘

Take that, GolfScript!

Answer 2

Python 124

r=raw_input()
l=range(len(r))
print', '.join(set('"'+r[i:j+1]+'"'for i in l for j in l if i<j and r[i:j+1]==r[i:j+1][::-1]))

Answer 3

Haskell 98, 88 91 96

import List
main=interact$show.filter(\x->length x>1&&x==reverse x).nub.(tails=<<).inits

Answer 4

Python - 138 136

This code does not duplicate sub-palindromes.

r=raw_input()
i,l=0,len(r)
j=l
a=[]
while i<l-1:
 t=r[i:j];j-=1
 if t==t[::-1]:a+=['"'+t+'"']
 if j<i+2:i+=1;j=l
print", ".join(set(a))

Answer 5

Ruby - 126 102 97 characters

s=gets
*m=*0..s.size
puts m.product(m).map{|h,j|(c=s[h,j+1]).size>1&&c==c.reverse ? c:0}.uniq-[0]

Answer 6

Golfscript, 48 characters

subpalindrome.gs

{,}{(;}/{{,}{);}/}%{+}*{.,1>\.-1%=*},.&{`}%", "*

Usage:

echo "12131331" | ruby golfscript.rb subpalindrome.gs

The first operation {,}{(;}/ turns a string into a list of trailing-substrings. A similar leading-substrings transform is then mapped over the result. Then flatten with {+}*, filter for palindromes using the predicate .,1>\.-1%=*, grab unique values with .&, then pretty print.

It would be neater to extract the trailing-substrings transform as a block and reuse it as a replacement for leading-substrings after reversing each trailing substring, but I can't figure out a succinct way of doing that.

Answer 7

Vyxal, 8 bytes

ǎU'Ḃ=nḢ∧

Try it Online!

ǎ        # All substrings
 U       # Uniquified
  '      # Filtered by...
   Ḃ=    # Is palindromic
       ∧ # And...
     nḢ  # Is 2+ letters

Answer 8

Haskell - 170, 153

import Data.List
import Data.Set
p a=fromList$[show x|x<-subsequences a,x==reverse x,length x>1]
main=getLine>>=(\x->putStrLn$intercalate", "$toList$p x)

Answer 9

J, 48

f=:,@:".
h=:\\.
~.(#~10&<)((]h-:"0&f|.h)#[:f]h)

eg

~.(#~10&<)((]h-:"0&f|.h)#[:f]h) '12131331'
121 131 313 1331 33

Answer 10

Prolog, 92

f(S,P):-append([_,X,_],S),X=[_,_|_],reverse(X,X),atom_codes(P,X).
p(S,R):-setof(P,f(S,P),R).

Sample use:

?- p("12131331",R).
R = ['121', '131', '1331', '313', '33'].

?- p("3333",R).
R = ['33', '333', '3333'].

Answer 11

Windows PowerShell, 104 109 111

0..($l=($s="$input").length-1)|%{($a=$_)..$l|%{-join$s[$a..$_]}}|sort -u|?{$_[1]-and$_-eq-join$_[$l..0]}

This expects the input on stdin and will throw all found palindromes one per line on stdout:

PS Home:\SVN\Joey\Public\SO\CG183> '12131331'| .\subp.ps1
33
121
131
313
1331

(When run from cmd it becomes echo 12131331|powershell -file subp.ps1 – it's just that $input takes a slightly different meaning depending on how the script was called, but it can be stdin, just not interactively.)

2011-01-30 13:57 (111) – First attempt.

2011-01-30 13:59 (109) – Inlined variable declaration.

2011-06-02 13:18 (104) – Redone substring finding by joining a char array instead of calling .Substring() and inlined a bit more.

Answer 12

Q, 78

{a::x;(?)(,/)b@'(&:')({x~(|:)x}'')b:-1_1_'({(sublist[;a]')x,'1+c}')c::(!)(#)a}

usage

q){a::x;(?)(,/)b@'(&:')({x~(|:)x}'')b:-1_1_'({(sublist[;a]')x,'1+c}')c::(!)(#)a}"12131331"
"121"
"131"
"313"
"1331"
"33"
q){a::x;(?)(,/)b@'(&:')({x~(|:)x}'')b:-1_1_'({(sublist[;a]')x,'1+c}')c::(!)(#)a}"3333"
"33"
"333"
"3333"

Answer 13

Retina, 34 27 bytes

&@!`(.)+.?(?<-1>\1)+(?(1)^)

Try it online!

The test suite needs an M because it is followed by another stage to insert empty lines between test cases.

Explanation

&@!`(.)+.?(?<-1>\1)+(?(1)^)

Print (!) all unique (@), overlapping (&) matches of the regex (.)+.?(?<-1>\1)+(?(1)^). This matches a palindrome of length 2 or more using balancing groups. There's a caveat to the "all overlapping matches" part: we can get at most one match per starting position. However, if two palindromes of different length begin at the same position, the shorter palindrome will appear again at the end of the longer palindrome. And since the greediness of + prioritises longer matches, we're getting all palindromes anyway.

Answer 14

05AB1E, 11 10 bytes

ŒÙʒÂQ}žQSK

Try it online!

Answer 15

Japt, 9 bytes

ã â fÅfêU

Try it

ã â fÅfêU     :Implicit input of string
ã             :Substrings
  â           :Deduplicate
    f         :Filter elements that return truthy
     Å        :  Slice off first character
       f      :Filter elements that return true
        êU    :  Test for palindrome

Answer 16

Perl, 112

$_=<>;chop;s/./$&$' /g;
map{/../&&$_ eq reverse&&$h{$_}++}split/ /
  for grep{s/./$`$& /g}split/ /;
print for keys %h

Answer 17

JavaScript (ES6), 120 bytes

a=>{for(b=0,c=d=a.length,e=[];b<d;--c<b+2?(b++,c=d):1)(f=a.slice(b,c))==f.split``.reverse().join``&&e.push(f);return e}

This function takes a string as input and outputs an array.

Answer 18

Clojure, 81 bytes

#(set(for[i(range 2(+(count %)1))p(partition i 1 %):when(=(reverse p)(seq p))]p))

for was a perfect match here :) Could use :when(=(reverse p)p) if input was a list of characters OR a full string didn't count as a palindrome, actually in that case the max range of i could be (count %) as well.

Most compact case for reference:

#(set(for[i(range 2(count %))p(partition i 1 %):when(=(reverse p)p)]p))

Answer 19

Python, 83 102 chars

s=lambda t:(t[1:]or())and(t,)*(t==t[::-1])+s(t[1:])+s(t[:-1])
print set(s(input()))

The phrase (t[1:]or())and... is equivalent to (...)if t[1:]else() and saves one character! I'm overly proud of this, given the savings.

Example:

python x
"51112232211161"
set(['11', '22', '11122322111', '161', '111', '112232211', '1223221', '22322', '232'])

Answer 20

Scala 127

object p extends App{val s=args(0);print(2.to(s.size).flatMap(s.sliding(_).toSeq.filter(c=>c==c.reverse)).toSet.mkString(" "))}

To keep this an apples to apples comparison with the other Scala answer, I also made mine an object that extends App. Rather than iterate the input string manually and use substring, I leveraged sliding() to create a sequence of all the substrings for me.

Answer 21

Scala 156 170

object o extends App{val l=args(0).length-2;val r=for(i<-0 to l;j<-i to l;c=args(0).substring(i,j+2);if(c==c.reverse))yield c;print(r.toSet.mkString(" "))}

object o{def main(s:Array[String]){val l=s(0).length-2;val r=for(i<-0 to l;j<-i to l;c=s(0).substring(i,j+2);if(c==c.reverse)) yield c;println(r.distinct.mkString(" "))}}

Answer 22

Perl 6,  35  32 bytes

{unique ~«m:ex/(.+).?<{$0.flip}>/}

Test it

{set ~«m:ex/(.+).?<{$0.flip}>/}

Test it

Expanded:

{  # bare block lambda with implicit parameter ｢$_｣

  set             # turn into a Set object (ignores duplicates)

  ~«\             # stringify ｢~｣ all of these ｢«｣ (possibly in parrallel)
                  # otherwise it would be a sequence of Match objects

  m               # match
  :exhaustive     # in every way possible
  /
    ( .+ )        # at least one character ｢$0｣
    .?            # possibly another character (for odd sized sub-palindromes)
    <{ $0.flip }> # match the reverse of the first grouping
  /
}

Answer 23

Perl, 43 40 bytes

Includes +1 for n

perl -nE 's/(?=((.)((?1)|.?)\2)(?!.*\1))/say$1/eg' <<< 12131331

Answer 24

Coconut, 69 bytes

def f(s)=s and{s*(s[::-1]==s>""<s[1:])}-{""}|f(s[1:])|f(s[:-1])or s{}

Try it online!

---

Python 2, 73 bytes

f=lambda s:s and{s*(s[::-1]==s>""<s[1:])}-{""}|f(s[1:])|f(s[:-1])or set()

Try it online!

Answer 25

Jelly, 9 bytes

ẆQŒḂÐfḊÐf

Try it online!

Answer 26

APL (Dyalog Classic), 27 bytes

{∪⍵/⍨≡∘⌽¨⍨⍵}∘⊃(,/1↓⍳∘≢,/¨⊂)

Try it online!

{∪⍵/⍨≡∘⌽¨⍨⍵}∘⊃(,/1↓⍳∘≢,/¨⊂)    Monadic train:
                           ⊂     Enclose the input, ⊂'12131331'
                     ⍳∘≢          Range from 1 to length of input
                     ⍳∘≢,/¨⊂      List of list of substrings of each length
                   1↓            Remove the first list (length-1 substrings)
               ⊃ ,/              Put the rest of the substrings into a single list.
{∪⍵/⍨≡∘⌽¨⍨⍵}                   To the result, apply this function which
                                   keeps all palindromes from a list:
      ≡∘⌽¨⍨⍵                    Boolean value of whether each (¨) string in argument
      ≡∘⌽ ⍨                     is equal to its own reverse

  ⍵/⍨                           Replicate (filter) argument by those values.
                                 This yields the length >1 palindromes.
∪                                Remove duplicates from the list of palindromes.

Answer 27

Japt, 14 bytes

Êò2@ãX fêSÃc â

Try it online!

Explanation:

Êò2               #Get the range [2...length(input)]
   @      Ã       #For each number in that range:
    ãX            # Get the substrings of the input with that length
       fêS        # Keep only the palindromes
           c      #Flatten
             â    #Keep unique results

Answer 28

PowerShell, 99 bytes

$args|% t*y|%{$s+=$_
0..$n|%{if($n-$_-and($t=-join$s[$_..$n])-eq-join$s[$n..$_]){$t}}
$n++}|sort -u

Try it online!

Less golfed:

$args|% toCharArray|%{
    $substring+=$_
    0..$n|%{
        if( $n-$_ -and ($temp=-join$substring[$_..$n]) -eq -join$substring[$n..$_] ){
            $temp
        }
    }
    $n++
}|sort -Unique

Answer 29

Brachylog, 11 bytes

{s.l>1∧.↔}ᵘ

Try it online!

(The header in the link is broken at the time of posting, so here's the predicate (function-equivalent in Brachylog) on only the first test case, with a w at the end to actually print the output.)

               The output is
{        }ᵘ    a list containing every possible unique
 s.            substring of
               the input
   l           the length of which
    >          is greater than
     1         one
      ∧        and
       .       which
        ↔      reversed
               is itself. (implicit output within the inline sub-predicate)

I feel like there's a shorter way to check that the length is greater than 1. (If it didn't filter out trivial palindromes, it would just be {s.↔}ᵘ.)

Answer 30

APL(NARS), 65 chars, 130 bytes

{0=≢m←∪b/⍨{1≥≢⍵:0⋄∧/⍵=⌽⍵}¨b←↑∪/{x[⍵;]⊂y}¨⍳≢x←11 1‼k k⊢k←≢y←⍵:⍬⋄m}

test:

  r←{0=≢m←∪b/⍨{1≥≢⍵:0⋄∧/⍵=⌽⍵}¨b←↑∪/{x[⍵;]⊂y}¨⍳≢x←11 1‼k k⊢k←≢y←⍵:⍬⋄m}
  o←⎕fmt
  o r '1234442'
┌2───────────┐
│┌2──┐ ┌3───┐│
││ 44│ │ 444││
│└───┘ └────┘2
└∊───────────┘
  o r '3333'
┌3───────────────────┐
│┌4────┐ ┌3───┐ ┌2──┐│
││ 3333│ │ 333│ │ 33││
│└─────┘ └────┘ └───┘2
└∊───────────────────┘
  o r  "12131331"
┌5─────────────────────────────────┐
│┌4────┐ ┌3───┐ ┌2──┐ ┌3───┐ ┌3───┐│
││ 1331│ │ 121│ │ 33│ │ 313│ │ 131││
│└─────┘ └────┘ └───┘ └────┘ └────┘2
└∊─────────────────────────────────┘
  o r '1234'
┌0─┐
│ 0│
└~─┘


{0=≢m←∪b/⍨{1≥≢⍵:0⋄∧/⍵=⌽⍵}¨b←↑∪/{x[⍵;]⊂y}¨⍳≢x←11 1‼k k⊢k←≢y←⍵:⍬⋄m}
 y←⍵  assign the argument to y (because it has to be used inside other function)
 x←11 1‼k k⊢k←≢y   assign the lenght of y to k, call the function 11 1‼k k
                   that seems here find all partition of 1 2 ..k
 {x[⍵;]⊂y}¨⍳≢      make partition of arg ⍵ using that set x
 ∪/                set union with precedent to each element of partition y (i don't know if this is ok)
 b←↑               get first assign to b
 {1≥≢⍵:0⋄∧/⍵=⌽⍵}¨ for each element of b return 1 only if the argument ⍵ is such that 
                   "∧/⍵=⌽⍵" ⍵ has all subset palindrome, else return 0
 b/⍨               get the elements in b for with {1≥≢⍵:0⋄∧/⍵=⌽⍵} return 1
 m←∪               make the set return without ripetition element, and assign to m
 0=≢               if lenght of m is 0 (void set) than 
 :⍬⋄m              return ⍬ else return m

it someone know better why, and can explain this better, free of change this all... I am not so certain of this code, possible if test examples are more numerous, something will go wrong...