Menemukan “sub-palindrom”.

24

Kode terpendek yang menemukan semua "sub-palindrom" string yang unik , yaitu: setiap substring dengan panjang> 1 yang merupakan palindrom.

mis.1

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

mis.2

input: "3333"
output: "33", "333", "3333"
Eelvex
sumber
1
Bisakah sebuah string menjadi sub-palindrome sendiri? Karena string adalah itu sendiri substring.
JPvdMerwe
@JPvdMerwe: Ya, tentu saja.
Eelvex
Sebenarnya yang lebih penting: apa yang harus menjadi output 333? Secara naif Anda akan mencetak 33dua kali
JPvdMerwe
@JPvdMerwe: '333' -> '33', '333'. Saya akan mengedit pertanyaan sesuai. Terima kasih.
Eelvex
Bagaimana outputnya ditentukan? Dibatasi koma dengan tanda kutip apakah masing-masing sub-palindrom seperti yang Anda tunjukkan di sini? Satu sub-p per baris?
Joey

Jawaban:

11

J, 24 31 40

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

Penggunaan sampel:

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

Ambillah itu, GolfScript!

JB
sumber
Akui saja, Anda hanya perlu membuang dari /dev/randomsini untuk membodohi kami ;-)
Joey
@ Joey coba sendiri; p (TBH, saya tidak percaya itu bisa berhasil pada awalnya)
JB
Saya cukup yakin itu kode aktual. Saya menghabiskan akhir pekan mencoba membungkus kepala saya dengan J, tetapi gagal total. Namun, saya mengenali kode; Saya hanya tidak mengerti apa fungsinya ;-)
Joey
2
Tidak bisakah ini disingkat menjadi ~.(#~(1<#*]-:|.)&>),<\\.(24 karakter)?
ephemient
@ephemient Memang. (Sepertinya saya terjebak dalam pola pikir "jawaban harus fungsi", yang tidak berlaku di sini.) Diedit, terima kasih!
JB
7

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]))
Alexandru
sumber
5

Haskell 98, 88 91 96

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

Python - 138 136

Kode ini tidak menduplikasi sub-palindrom.

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))
JPvdMerwe
sumber
1
Ubah '"'+t+'"'untuk tmenghemat ruang, meskipun menggunakan tanda kutip tunggal.
Thomas O
3

Ruby - 126 102 97 karakter

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]
Nemo157
sumber
3

Golfscript, 48 karakter

subpalindrome.gs

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

Pemakaian:

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

Operasi pertama {,}{(;}/mengubah string menjadi daftar trailing-substring. Transformasi leading-substring serupa kemudian dipetakan pada hasilnya. Kemudian rata dengan {+}*, filter untuk palindrom menggunakan predikat .,1>\.-1%=*, ambil nilai unik dengan .&, lalu cetak cantik.

Akan lebih rapi untuk mengekstrak transformasi trailing-substring sebagai blok dan menggunakannya kembali sebagai pengganti untuk substring terkemuka setelah membalik setiap substring trailing, tetapi saya tidak dapat menemukan cara ringkas untuk melakukan itu.

gelandangan
sumber
2

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)
Jonathan Sternberg
sumber
Ganti main=getLine>>=(\x->putStrLn$intercalate", "$toList$p x)dengan main=getLine>>=putStrLn.intercalate", ".toList.p. Saya juga akan mengganti panggilan pdengan tubuhnya.
Yasir Arsanukaev
Substring / = subsequences! Program Anda melaporkan lebih banyak subpalindrom daripada keluaran referensi misalnya 1. ("1111" misalnya)
JB
2

J, 48

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

misalnya

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

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

Penggunaan sampel:

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

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

Windows PowerShell, 104 109 111

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

Ini mengharapkan input pada stdin dan akan membuang semua palindrom yang ditemukan satu per baris pada stdout:

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

(Ketika lari dari cmditu menjadi echo 12131331|powershell -file subp.ps1- Hanya saja itu $inputmengambil arti yang sedikit berbeda tergantung pada bagaimana skrip dipanggil, tetapi bisa stdin, hanya saja tidak secara interaktif.)

2011-01-30 13:57 (111) - Upaya pertama.

2011-01-30 13:59 (109) - Deklarasi variabel inline.

2011-06-02 13:18 (104) - Mengulangi pencarian substring dengan bergabung dengan array char alih-alih memanggil .Substring()dan menambahkan sedikit lebih banyak.

Joey
sumber
2

Q, 78

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

pemakaian

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"
tmartin
sumber
2

Retina , 34 27 byte

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

Cobalah online!

Test suite perlu Mkarena diikuti oleh tahap lain untuk memasukkan garis kosong di antara kasus uji.

Penjelasan

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

Cetak ( !) semua kecocokan unik ( @), tumpang tindih ( &) dari regex (.)+.?(?<-1>\1)+(?(1)^). Ini cocok dengan palindrome dengan panjang 2 atau lebih menggunakan kelompok penyeimbang. Ada peringatan untuk bagian "semua pertandingan yang tumpang tindih": kita bisa mendapatkan paling banyak satu pertandingan per posisi awal. Namun, jika dua palindrom dengan panjang yang berbeda mulai pada posisi yang sama, palindrom yang lebih pendek akan muncul lagi di ujung palindrom yang lebih panjang. Dan karena keserakahan dari +prioritises cocok lebih lama, kita tetap mendapatkan semua palindrom.

Martin Ender
sumber
2

05AB1E , 11 10 byte

ŒÙʒÂQ}žQSK

Cobalah online!

Guci Gurita Ajaib
sumber
1
9 byte
scottinet
@ skottinet gagal untuk lajang, EG1234142141410010101000
Magic Octopus Mm
1
Milik Anda juga, tetapi tidak dengan cara yang sama. o_O Ada sesuatu yang terjadi yang perlu diselidiki. Sementara itu, di sini adalah versi 10 byte yang tampaknya berfungsi
scottinet
Ada bug dengan uniquify, saya memperbaikinya. Sekarang kedua 11 byte jawaban Anda dan 9 byte satu pekerjaan saya :-)
scottinet
@ skottinet 10-byter Anda bisa menjadi 9-byter dengan mengubah 1›ke . :)
Kevin Cruijssen
1

Perl, 112

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

JavaScript (ES6), 120 byte

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}

Fungsi ini mengambil string sebagai input dan output array.

Luke
sumber
1

Clojure, 81 byte

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

foradalah pasangan yang sempurna di sini :) Dapat digunakan :when(=(reverse p)p)jika input adalah daftar karakter ATAU string penuh tidak dihitung sebagai palindrom, sebenarnya dalam hal itu kisaran maksimum ibisa (count %)juga.

Kasing paling ringkas untuk referensi:

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

Python, 83 102 karakter

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

Frasa (t[1:]or())and...ini setara dengan (...)if t[1:]else()dan menyimpan satu karakter! Saya terlalu bangga dengan ini, mengingat penghematannya.

Contoh:

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

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(" "))}

Untuk menjaga agar perbandingan apel dengan apel ini dengan jawaban Scala lainnya, saya juga menjadikan saya objek yang memperluas Aplikasi. Daripada mengulangi string input secara manual dan menggunakan substring, saya meningkatkan sliding () untuk membuat urutan semua substring untuk saya.

bkuder
sumber
1

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(" "))}}

Lalith
sumber
Hai Lalith, saya sedikit mempersingkat kode Anda: Tidak kosong sebelum menghasilkan dan memperluas Aplikasi alih-alih menimpa utama, println => cetak dan berbeda => toSet
pengguna tidak diketahui
1

Perl 6 ,  35  32 byte

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

Menguji

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

Menguji

Diperluas:

{  # 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
  /
}
Brad Gilbert b2gills
sumber
1

Jelly , 9 byte

ẆQŒḂÐfḊÐf

Cobalah online!

Erik the Outgolfer
sumber
Output dari permalink Anda salah.
Dennis
@Dennis mengapa ini menjadi target dupe kemudian> _> diperbaiki
Erik the Outgolfer
7 byte dengan Jelly baru.
user202729
1

APL (Dyalog Classic) , 27 byte

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

Cobalah 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.
lirtosiast
sumber
Karena OP memanggil "kode", snippet ∪w/⍨≡∘⌽¨⍨w←⊃,/1↓(⍳∘≢,/¨⊂)tersebut valid.
Adám
@ Adm Saya pikir saya akan menyimpan jawaban ini karena demi standar situs modern, terutama karena tidak mendapatkan kemenangan secara keseluruhan.
lirtosiast
1

Japt , 14 byte

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

Cobalah online!

Penjelasan:

Êò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
Kamil Drakari
sumber
1

PowerShell , 99 byte

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

Cobalah online!

Kurang bermain golf:

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

Brachylog , 11 byte

{s.l>1∧.↔}ᵘ

Cobalah online!

(Header di tautan rusak pada saat posting, jadi inilah predikatnya (fungsi-setara di Brachylog) hanya pada case uji pertama, dengan wdi bagian akhir untuk benar-benar mencetak 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)

Saya merasa ada cara yang lebih pendek untuk memeriksa bahwa panjangnya lebih besar dari 1. (Jika tidak menyaring palindrom sepele, itu hanya akan menjadi {s.↔}ᵘ.)

String yang tidak terkait
sumber
1

APL (NARS), 65 karakter, 130 byte

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

uji:

  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

itu seseorang yang tahu lebih baik mengapa, dan dapat menjelaskan ini lebih baik, bebas dari perubahan ini semua ... Saya tidak begitu yakin dengan kode ini, mungkin jika contoh uji lebih banyak, ada yang salah ...

RosLuP
sumber
1

Japt , 9 byte

ã â fÅfêU

Cobalah

ã â 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
Shaggy
sumber
0

Java 8, 202 201 199 byte

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;}

Coba di sini.

Jika fungsi tidak diizinkan dan program lengkap diperlukan, itu 256 256 253 byte sebagai gantinya:

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);}}

Coba di sini.

Penjelasan:

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
Kevin Cruijssen
sumber
0

JavaScript (ES6), 107 byte

Mengembalikan 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))

Uji kasus

Arnauld
sumber