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

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 8

05AB1E, 11 10 bytes

ŒÙʒÂQ}žQSK

Try it online!

Answer 9

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 10

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 11

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 12

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 13

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 14

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 15

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 16

Jelly, 9 bytes

ẆQŒḂÐfḊÐf

Try it online!

Answer 17

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 18

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 19

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 20

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

Answer 21

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 22

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 23

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 24

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 25

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 26

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 27

Perl, 112

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

Answer 28

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 29

Java 8, 202 201 199 bytes

import java.util.*;s->{Set r=new HashSet();String x;for(int l=s.length(),i=0,j;i<l;i++)for(j=i;++j<=l;)if((x=s.substring(i,j)).contains(new StringBuffer(x).reverse())&x.length()>1)r.add(x);return r;}

Try it here.

If a function isn't allowed and a full program is required, it's 256 255 253 bytes instead:

import java.util.*;interface M{static void main(String[]a){Set r=new HashSet();String x;for(int l=a[0].length(),i=0,j;i<l;i++)for(j=i;++j<=l;)if((x=a[0].substring(i,j)).contains(new StringBuffer(x).reverse())&x.length()>1)r.add(x);System.out.print(r);}}

Try it here.

Explanation:

import java.util.*;      // Required import for Set and HashSet

s->{                     // Method with String parameter and Set return-type
  Set r=new HashSet();   //  Return-Set
  String t;              //  Temp-String
  for(int l=s.length(),  //  Length of the input-String
          i=0,j;         //  Index-integers (start `i` at 0)
      i<l;i++)           //  Loop (1) from `0` to `l` (exclusive)
    for(j=i;++j<=l;)     //   Inner loop (2) from `i+1` to `l` (inclusive)
      if((t=s.substring(i,j) 
                         //    Set `t` to the substring from `i` to `j` (exclusive)
         ).contains(new StringBuffer(t).reverse())
                         //    If this substring is a palindrome,
         &t.length()>1)  //    and it's length is larger than 1:
        r.add(t);        //     Add the String to the Set
                         //   End of inner loop (2) (implicit / single-line body)
                         //  End of loop (1) (implicit / single-line body)
  return r;              //  Return the result-Set
}                        // End of method

Answer 30

JavaScript (ES6), 107 bytes

Returns a Set.

s=>new Set((g=(s,r=[...s].reverse().join``)=>s[1]?(r==s?[s]:[]).concat(g(s.slice(1)),g(r.slice(1))):[])(s))

Test cases

let f =

s=>new Set((g=(s,r=[...s].reverse().join``)=>s[1]?(r==s?[s]:[]).concat(g(s.slice(1)),g(r.slice(1))):[])(s))

console.log([...f('12131331').values()])
console.log([...f('3333').values()])

Answer 31

Perl, 43 40 bytes

Includes +1 for n

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