Temukan Substring Privileged

8

String Istimewa

Himpunan string istimewa didefinisikan secara rekursif sebagai berikut.

  • Semua string dengan panjang 0 atau 1 adalah hak istimewa.
  • Sebuah string sdengan panjang minimal 2 adalah privilege, jika ada string privilege yang lebih pendek tyang muncul stepat dua kali, sekali sebagai awalan dan sekali sebagai akhiran. Kejadian yang tumpang tindih dihitung sebagai berbeda.

Misalnya, string aa, aaadan abadiberi hak istimewa, tetapi abdan aabtidak.

Memasukkan

String alfanumerik.

Keluaran

Semua substring istimewa dari string input, masing-masing tepat sekali, dalam urutan apa pun. Output dapat diberikan dalam format array asli bahasa Anda (atau setara terdekat), atau dicetak satu substring per baris.

Fakta yang menyenangkan

Jumlah string dalam output selalu tepat length(s) + 1( sumber ).

Aturan

Fungsi dan program lengkap diizinkan. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Uji Kasus

Ini disortir terlebih dahulu berdasarkan panjang dan kemudian menurut abjad, tetapi urutan apa pun dapat diterima.

"" -> [""]
"a" -> ["","a"]
"abc" -> ["","a","b","c"]
"abcaaabccaba" -> ["","a","b","c","aa","cc","aaa","aba","abca","abcca","bccab","bcaaab","caaabc"]
"1010010110101010001101" -> ["","0","1","00","11","000","010","101","0110","1001","01010","10001","10101","010010","101101","0101010","1010101","01011010","10100101","1010001101","1101010100011","00101101010100","011010101000110"]
"CapsAndDigits111" -> ["","1","A","C","D","a","d","g","i","n","p","s","t","11","111","igi","sAndDigits"]

Papan peringkat

Berikut adalah papan peringkat berdasarkan bahasa, milik Martin Büttner .

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

# Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Tampilkan cuplikan kode

code-golf string Zgarb
sumber
Dapatkah output dipisahkan oleh ruang atau harus dipisahkan oleh baris baru? (jika mencetak)
Sp3000
@ Sp3000 Ini harus berupa baris baru, atau bahasa Anda mencetak array string.
Zgarb
2
Jadi Anda meminta kami untuk memeriksa string istimewa Anda?
imallett
mengapa definisi yang begitu panjang? Tidak bisakah Anda menulis dengan ekuivalen "string priveliged adalah string yang dimulai dan diakhiri dengan simbol yang sama, kata simbol yang tidak terjadi di tempat lain di string"? =)
Mints97
1
@ Mints97 String yang lebih pendek tmungkin bukan simbol tunggal. Sebagai contoh, aaaadalah string istimewa, karena memiliki aaawalan dan akhiran, dan itu terjadi hanya dua kali. Saya menambahkannya sebagai contoh.
Zgarb

Jawaban:

4

.NET Regex, 31 byte

(?=(((?<=(\3\2|)).+?(?<=\3))*))

String ditangkap di \1dalam setiap pertandingan.

Penjelasan

(?=                             # Lookahead. This makes it possible to catch overlapped
                                #   strings in \1.
    (                           # The captured group \1 for result.
        (                       # Match 0 or more occurrences.
            (?<=(\3\2|))        # Set \3 to the string from last \3 to the current position,
                                #   or an empty string for the first time.
            .+?(?<=\3)          # Match a shortest nonempty string so that the whole string
                                #   from the beginning to the current position ends with \3.
        )*
    )
)
jimmy23013
sumber
5

CJam, 33 45 39 38 byte

l_,,\f>{(0{:U2$>2$2$#):T<+UT+T}g;\;N}%

Katakanlah itu dicetak tanpa baris baru. Jadi baris tambahan berarti substring kosong ...

Penjelasan

l              " Read one line. ";
_,,            " Get an array of 0 to array length-1. ";
\f>            " Get all nonempty suffixes. ";
{              " For each suffix: ";
    (          " Extract the first character. Say the first character X and the rest Y. ";
    0          " Push U = 0. ";
    {          " Do: ";
        :U     " Set variable U. ";
        2$>    " Z = Y with first U characters removed. ";
        2$2$#  " Find X in Y, or return -1 if not found. ";
        ):T    " Increment and save it in T. ";
        <+     " Append the first T characters of Z to X. ";
        UT+    " U += T. ";
        T      " Push T. ";
    }g         " ...while T is nonzero. ";
    ;\;        " Discard U and Y. ";
    N          " Append a newline. ";
}%
jimmy23013
sumber
4

Python 2, 179 173 164 byte

exec"f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n%s);g=lambda s:filter(f,{''}|{s[i:j+1]for i%sfor j%s})"%((" in range(len(s))",)*3)

Cukup besar saat ini - Saya ingin tahu apakah mungkin untuk menggabungkan cek dan generasi substring entah bagaimana ...

Lambda fpada dasarnya adalah suatu is_privileged()fungsi, menggabungkan tiga kondisi menjadi satu perbandingan (substring diistimewakan, muncul dua kali, adalah akhiran dan awalan).

Diperluas:

f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n in range(len(s)))
g=lambda s:filter(f,{''}|{s[i:j+1]for i in range(len(s))for j in range(len(s))})
Sp3000
sumber
3

Python 3, 131 129 byte

f=lambda s,p={''}:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)or list(p)

Ini secara rekursif menemukan substring istimewa, dimulai dengan substring terpendek dan menambahkannya ke set. Set kemudian digunakan dalam menentukan apakah substring yang lebih panjang memiliki hak istimewa.

Sayangnya, ini adalah fungsi sekali pakai saja. Berikut program lengkap yang sesuai ( 145 byte ):

p={''}
f=lambda s:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)
f(input())
print(list(p))
grc
sumber
3

Python, 152 147 126 116 byte

def n(s):
 w='';t=[w]
 for a in s:w+=a;t+=[w[w.rfind(w[-max(len(q)for q in t if w.endswith(q)):],0,-1):]]
 return t

Seperti ditunjukkan dalam makalah yang ditautkan, ada akhiran hak istimewa yang unik untuk setiap awalan string. Sufiks itu adalah bentuk di p·u·pmana psubstring istimewa terlama yang sebelumnya ditemukan yang merupakan sufiks dari awalan. (Pencarian adalah argumen untuk max, yang sebenarnya menemukan panjang pkarena lebih mudah dilakukan maxdaripada longest.) Setelah pditemukan, akhiran itu sendiri dibentuk dengan mencari kejadian terakhir kedua pdalam awalan, menggunakan rfinddibatasi untuk tidak menggunakan karakter terakhir. Kita tahu itu akan berhasil, karena itu padalah sufiks yang sebelumnya ditemukan. (Bukti algoritma yang lebih ketat dapat diturunkan dari makalah.)

Saya cukup yakin bahwa ini dapat diimplementasikan dalam waktu linier menggunakan pohon suffix, bukan algoritma kuadratik yang digunakan di atas, tetapi program di atas tentu cukup cepat di semua kasus uji, dan menangani string 2000 as dalam sebuah sedikit kurang dari satu detik di laptop saya (tidak superpower).

rici
sumber
2

Ruby, 87

Saya merasa seperti ada solusi regex rekursif di sini di suatu tempat, tapi saya tidak terlalu pandai dalam hal itu, jadi inilah fungsi rekursif yang sangat lambat dan panjang.

f=->s{s[/./]?(o=f[$']|f[s.chop];o.any?{|t|s[/^#{t}/]&&s[/.#{t}/]&&!$'[0]}&&o<<s;o):[s]}

Algoritma kira-kira sama dengan grc , dibuat lebih lambat (tapi lebih pendek) dengan karakter tunggal yang tidak khusus. String karakter tunggal dapat dianggap istimewa karena memiliki string kosong sebagai awalan, akhiran, dan tempat lain.

Trik menarik lainnya di sini adalah penggunaan $', variabel ajaib yang diwarisi dari Perl yang mengambil nilai string setelah pencocokan ekspresi reguler terbaru. Ini memberi saya cara singkat untuk memotong karakter pertama dari sebuah string, meskipun saya mendapatkan hampir semua karakter tersebut dengan harus mengaturnya dengan s[/./]alih - alih s[0]. Saya menggunakannya lagi untuk memeriksa bahwa kecocokan substring kedua terjadi pada akhir string.

histokrat
sumber
1

J, 92 byte

Butuh beberapa detik pada input terpanjang.

pmemeriksa apakah string diistimewakan (dengan rekursi), smemeriksa setiap substring menggunakan p.

   p=.1:`(+./@:(($:@>@{.*((2=+/)*1={:)@{.@=)@(<\))~i.@#)@.(1<#)
   s=.3 :'~.a:,,(<@#~p)\.\y'

Tes:

   s 'CapsAndDigits111'
┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬───┬─┬──────────┬─┬──┬───┐
││C│a│p│s│A│n│d│D│i│g│igi│t│sAndDigits│1│11│111│
└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴───┴─┴──────────┴─┴──┴───┘       

   input =. '';'a';'ab';'abc';'abcaaabccaba';'1010010110101010001101';'CapsAndDigits111'

   s each input
┌──┬────┬──────┬────────┬─────────────────────────────────────────────────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┬────────────────────...
│┌┐│┌┬─┐│┌┬─┬─┐│┌┬─┬─┬─┐│┌┬─┬─┬─┬────┬──┬───┬──────┬──────┬──┬─────┬─────┬───┐│┌┬─┬─┬───┬───┬──┬────┬──────┬────────┬──┬────┬──────┬────────┬─────┬─────┬───────┬───────┬──────────────┬───┬─────┬─────────────┬───────────────┬──────────┐│┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬...
││││││a││││a│b││││a│b│c││││a│b│c│abca│aa│aaa│bcaaab│caaabc│cc│abcca│bccab│aba││││1│0│101│010│00│1001│010010│10100101│11│0110│101101│01011010│10101│01010│1010101│0101010│00101101010100│000│10001│1101010100011│011010101000110│1010001101││││C│a│p│s│A│n│d│D│i│...
│└┘│└┴─┘│└┴─┴─┘│└┴─┴─┴─┘│└┴─┴─┴─┴────┴──┴───┴──────┴──────┴──┴─────┴─────┴───┘│└┴─┴─┴───┴───┴──┴────┴──────┴────────┴──┴────┴──────┴────────┴─────┴─────┴───────┴───────┴──────────────┴───┴─────┴─────────────┴───────────────┴──────────┘│└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴...
└──┴────┴──────┴────────┴─────────────────────────────────────────────────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┴────────────────────...

   #@s each input NB. number of strings in outputs
┌─┬─┬─┬─┬──┬──┬──┐
│1│2│3│4│13│23│17│
└─┴─┴─┴─┴──┴──┴──┘

   # each input NB. input lengths
┌─┬─┬─┬─┬──┬──┬──┐
│0│1│2│3│12│22│16│
└─┴─┴─┴─┴──┴──┴──┘
randomra
sumber
1

JavaScript (ES6) 195

Fungsi P secara rekursif memverifikasi bahwa string memiliki hak istimewa.
Fungsi F mencoba setiap substring yang terkandung dalam string yang diberikan. String yang ditemukan disimpan sebagai kunci hashtable untuk menghindari duplikat.
Akhirnya, kunci dikembalikan sebagai output.

F=a=>{
  P=(s,l=s.length,r=l<2,j=1)=>{
    for(;!r&&j<l;j++)s.indexOf(x=s.slice(0,j),1)+j-l||(r=P(x));
      return r
  };      
  for(o={'':l=i=0};a[i+l]||a[i=0,++l];)
    if(P(p=a.slice(i++,i+l)))
      o[p]=0;
  return[a for(a in o)]
}
edc65
sumber