Memasukkan

String alfanumerik s.

Keluaran

String terpendek yang muncul tepat sekali sebagai substring (bersebelahan) di s. Kejadian yang tumpang tindih dihitung sebagai berbeda. Jika ada beberapa kandidat dengan panjang yang sama, Anda harus menampilkan semuanya dalam urutan kejadian. Dalam tantangan ini, string kosong muncul n + 1kali dalam string panjang n.

Contoh

Pertimbangkan senarnya

"asdfasdfd"

String kosong muncul 10 kali di dalamnya, jadi itu bukan kandidat untuk kejadian unik. Masing-masing huruf "a", "s", "d", dan "f"terjadi setidaknya dua kali, sehingga mereka tidak kandidat baik. Substring "fa"dan "fd"terjadi hanya sekali dan dalam urutan ini, sedangkan semua substring panjang 2 lainnya terjadi dua kali. Dengan demikian output yang benar adalah

["fa","fd"]

Aturan

Baik fungsi dan program penuh diizinkan, dan celah standar tidak. Pemformatan yang tepat dari output fleksibel, masuk akal. Khususnya, tidak menghasilkan output untuk string kosong diperbolehkan, tetapi tidak menghasilkan kesalahan. Hitungan byte terendah menang.

Uji kasus

"" -> [""]
"abcaa" -> ["b","c"]
"rererere" -> ["ererer"]
"asdfasdfd" -> ["fa","fd"]
"ffffhhhhfffffhhhhhfffhhh" -> ["hffff","fffff","hhhhh","hfffh"]
"asdfdfasddfdfaddsasadsasadsddsddfdsasdf" -> ["fas","fad","add","fds"]

Papan peringkat

Inilah papan peringkat berdasarkan bahasa yang saya janjikan.

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

<script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>site = 'meta.codegolf',postID = 5314,isAnswer = true,QUESTION_ID = 45056;jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)<\\/code><\/pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Pyth, 27 26 byte

&zhfTmf!/>zhxzYYm<>zkdUzUz

Coba di sini.

Perhatikan bahwa karena bug dalam kompiler online, case string kosong hanya berfungsi dengan benar pada versi baris perintah, yang dapat ditemukan di sini.

Anda juga dapat menyembuhkan bug dengan memberikan baris baru sebagai input untuk kompiler online.

Penjelasan:

                                   z = input(), implicit.
&z                                 Prints empty string if input is empty.
  hfT                              Take the first non-empty list from
     m                  Uz         A list of list of substrings of z, divided by length
                m<>zkdUz           with some shorter strings repeated later, to no effect.
      f                            Where the substrings are filtered on
       !/      Y                   There being 0 occurrences of the substring in
         >z                        The slice of z
           hxzY                    from the character after the first character
                                   of the first occurrence of the substring in z
                                   to the end of z.

Python 3, 124 123 111 96 byte

f=lambda s,n=1:[x for x in[s[i:i+n]for i in range(len(s)+1)]if s.find(x)==s.rfind(x)]or f(s,n+1)

Mencari string sehingga kemunculan pertama dari kiri sama dengan kemunculan pertama dari kanan. Di +1dalam rangeadalah untuk mengakomodasi untuk kasus string kosong.

Sekarang jika hanya Python .count()yang menghitung pertandingan yang tumpang tindih , maka ini akan menjadi sedikit lebih pendek.

Mathematica, 95 94 79 byte

Cases[Tally@StringCases[#,___,Overlaps->All],{s_,1}:>s]~MinimalBy~StringLength&

StringCasesmemberi saya semua kemungkinan substring, Tallydan Casesmenyaring yang muncul lebih dari satu kali dan MinimalBymenemukan yang paling pendek.

GolfScript, 44 byte

:S;-1:x{;S,x):x-),{S>x<}%:^1/{^\/,2=},.!}do`

Mengambil input sebagai string pada stdin dan output dalam sintaks array-ganda: mis [["b"] ["c"]]. Demo online

Pembedahan

:S;          # Store input in S and pop it
-1:x         # Store -1 in x
{            # do-while loop
  ;          #   Pop x the first time and [] every subsequent time
  S,x):x-),  #   Increment x and build an array [0 1 ... len(S)-x]
  {S>x<}%    #   Map that array to [substr(S,0,x) substr(S,1,x) ...]
  :^         #   Store in ^ (to avoid the token coalescing with the next char)
  1/         #   Split by length 1 to iterate over 1-elt arrays rather than strings
  {^\/,2=},  #   Filter to arrays which occur exactly once as a subarray of ^
  .!         #   Duplicate and test emptiness
}do          # end do-while loop: loop if the filtered array is empty
`            # Stringify for output

Ini diatur sedemikian rupa sehingga tidak diperlukan case khusus untuk string kosong (yang saya sertakan sebagai test case dalam demo online yang ditautkan di atas).

CJam, 52 43 40 byte

]]q:Q,,{)Q,1$-),f{Q><}:R{R\a/,2=},}%{}=p

Input adalah string tanpa tanda kutip

Penjelasan :

]]                                       "For empty string input case";
  q:Q                                    "Read the input and store in Q";
     ,,                                  "Take length of input and 0 to length array";
       {                          }%     "Map the above array on this code block";
        )Q                               "Increment the number in the current iteration, L";
         Q,1$                            "Take input's length and copy the above number";
             -)                          "Get upper limit of next loop to get substrings";
               ,f{   }                   "Get 0 to above number array and for each";
                  Q><                    "Get the L length substring at Ith index where";
                                         "I loops from 0 to Q, - L + 1";
                      :R                 "Store this list of substring of length L in R";
                        {R\a/,2=},       "Filter to get unique substrings";
                                    {}=  "Get the first non empty substring array";
                                         "This leaves nothing on stack if all are empty";
                                       p "Print the top stack element. At this point, its";
                                         "Either the first non empty substring array or";
                                         "the ]] i.e. [""] which we added initially";

Contoh:

asdfdfasddfdfaddsasadsasadsddsddfdsasdf

Keluaran

["fas" "fad" "add" "fds"]

Cobalah online di sini

Scala, 120 byte

readLine.inits.flatMap(_.tails).toList.groupBy(l=>l).filter(x=>x._2.length<2).map(_._1).groupBy(_.length).minBy(_._1)._2

Saya mulai dengan 140 yang setidaknya sudah pas dengan tweet.

(                                        // added for comments
 readLine                                // input
.inits.flatMap(_.tails).toList           // get all substrings of that string
.groupBy(l=>l).filter(x=>x._2.length<2)  // remove substrings that occur more than once
.map(_._1).groupBy(_.length)             // take the substring and group by length
.minBy(_._1)._2                          // take the list of shortest substrings
)

JavaScript (ES6), 109 110

Edit pencarian daripada indexOf, karena string input adalah alfanumerik. Terima kasih @IsmaelMiguel

Fungsi rekursif, mencari substring mulai dengan panjang 1 dan naik.

F=(s,n=1,r)=>
s?[...s].map((a,i)=>~s.indexOf(a=s.substr(i,n),s.search(a)+1)?r:r=[...r||[],a])&&r||F(s,n+1):[s]

Tidak diikat dan dijelaskan

 F = function(s, n=1) { // start with length 1
   var i, a, p, r;
   if (s == "") // special case for empty input string
     return [s];
   for (i = 0; i < s.length; i++) 
   // for each possibile substring of length n
   // (should stop at s.length-n+1 but going beyond is harmless)
   // Golfed: "[...s].map((a,i)" ... using i, a is overwrittem
   {
     a = s.substr(i, n); // substring at position i
     p = s.search(a); // p is the first position of substring found, can be i or less
     p = s.indexOf(a, p + 1) // p is now the position of a second instance of substring, or -1 if not found
     if (~p) // ~p is 0 if p is -1
     {
       ; // found more than once, do nothing
     }
     else
     {
       r = r || []; // if r is undefined, then it becomes an empty array
       r.push(a); // save substring 
       // Golfed: "r=[...r||[],a]"
     }
   }
   if (r) // if found some substring, saved in r
   {
     return r;
   }
   return F(s, n+1) // recursive retry for a bigger length
 }

Uji di konsol FireFox / FireBug

;["", "abcaa", "rererere", "asdfasdfd", "ffffhhhhfffffhhhhhfffhhh", 
 "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"]
.forEach(x=>console.log(x,F(x)))

Keluaran

 [""]
abcaa ["b", "c"]
rererere ["ererer"]
asdfasdfd ["fa", "fd"]
ffffhhhhfffffhhhhhfffhhh ["hffff", "fffff", "hhhhh", "hfffh"]
asdfdfasddfdfaddsasadsasadsddsddfdsasdf ["fas", "fad", "add", "fds"]

Jawa, 168 176 233

Berikut adalah contoh loop bersarang yang cukup mendasar.

void n(String s){for(int l=0,i=0,t=s.length(),q=0;l++<t&q<1;i=0)for(String b;i<=t-l;)if(s.indexOf(b=s.substring(i,i+++l),s.indexOf(b)+1)<0){System.out.println(b);q++;}}

Atau sedikit lebih mudah dibaca:

void t(String s){
    for(int l=0,i=0,t=s.length(),q=0;l++<t&q<1;i=0)
        for(String b;i<=t-l;)
            if(s.indexOf(b=s.substring(i,i++ +l),s.indexOf(b)+1)<0){
                System.out.println(b);
                q++;
            }
}

Haskell, 169 162 155 153 151 138 120 120 115

import Data.List
l=length
q k=filter$(==)k.l
p y=q(minimum.map l$y)$y
f x=p$concat$q 1$group$sort$(tails x>>=inits)

Untuk menggunakannya:

f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"

Pemberian yang mana:

["add","fad","fas","fds"]

Btw. Saya benci baris terakhir dari kode saya (pengulangan h y). Adakah yang mengisyaratkan untuk menyingkirkannya?

J, 61 58 44 42 40 38 37 byte

[:>@{.@(#~#@>)#\<@(~.#~1=#/.~)@(]\)]

Berikut adalah versi yang dibagi menjadi komponen-komponen terpisah dari solusi:

unqs =. ~. #~ 1 = #/.~               NB. uniques; items that appear exactly once
allsbsq =. #\ <@unqs@(]\) ]        NB. all unique subsequences
shrtsbsq =. [: >@{.@(#~ #@>) allsbsq NB. shortest unique subsequence

• x #/. ymenghitung untuk setiap elemen berbeda dalam xseberapa sering di terjadi di y. Jika kita menggunakan ini sebagai y #/. y, kita mendapatkan untuk setiap elemen berbeda dalam yhitungannya. Misalnya, a #/. auntuk a =. 1 2 2 3 4 4hasil 1 2 1 2.
• 1 = ymemeriksa item mana yyang sama dengan 1. Misalnya, 1 = a #/. ahasil 1 0 1 0.
• u~adalah refleksif dari kata kerja monadik u. Ini, u~ ysama dengan y u y. Jadi, #/.~ ysama dengan #/.~ y. Ketika diterapkan pada kata kerja diad, u~adalah pasif dari u. Artinya, x u~ ysama dengan y u x. Ini digunakan di beberapa tempat lain yang tidak saya sebutkan secara eksplisit.
• ~. yadalah inti dari y, sebuah vektor dengan duplikat dihapus. Misalnya, ~. ahasil 1 2 3 4.
• x # y( salin ) memilih dari yitem pada indeks di mana xberisi a 1.
• Dengan demikian, (1 = y #/. y) # (~. y)buat vektor elemen-elemen yyang hanya muncul sekali. Dalam notasi diam-diam, kata kerja ini ditulis sebagai ~. #~ 1 = #/.~; sebut saja frasa ini unqsuntuk penjelasan selanjutnya.

• x ]\ ymenciptakan sebuah array xdengan 1 + y - xsemua infiks vektor ypanjang x. Misalnya, 3 ]\ 'asdfasdfdhasil

  asd
  sdf
  dfa
  fas
  asd
  sdf
  dfd
  

• # yadalah penghitungan dari y, yaitu jumlah elemen dalam y.

• u\ yberlaku uuntuk setiap awalan dari y. Kebetulan, #\ ymembuat vektor bilangan bulat dari 1ke #y.
• < ymenempatkan yke dalam kotak. Ini diperlukan karena array tidak dapat di-compang-camping dan kami menghitung array sufiks dengan panjang yang berbeda; array kotak dihitung sebagai skalar.

• Dengan demikian, (i. # y) <@:unqs@(]\) ymenghasilkan vektor #yarray kotak panjang k (untuk semua 0 ≤ k < #y) infiks y yang terjadi tepat sekali. Bentuk diam-diam dari kata kerja ini adalah i.@# <@unqs@(]\) ]atau i.@# <@(~. #~ 1 = #/.~)@(]\) ]jika kita tidak menggunakan unqsnamanya. Sebut frasa ini allsbsquntuk penjelasan selanjutnya. Misalnya, allsbsq 'asdfasdfd'hasil:

  ┌┬─┬──┬───┬────┬─────┬──────┬───────┬────────┐
  ││ │fa│dfa│sdfa│asdfa│asdfas│asdfasd│asdfasdf│
  ││ │fd│fas│dfas│sdfas│sdfasd│sdfasdf│sdfasdfd│
  ││ │  │dfd│fasd│dfasd│dfasdf│dfasdfd│        │
  ││ │  │   │sdfd│fasdf│fasdfd│       │        │
  ││ │  │   │    │asdfd│      │       │        │
  └┴─┴──┴───┴────┴─────┴──────┴───────┴────────┘
  

• (#@> y) # ymengambil dari vektor array kotak yyang tidak kosong.

• {. ymengambil elemen pertama vektor y.
• > ymenghapus kotak dari y.
• Dengan demikian, > {. (#@> y) # ymenghasilkan array non-kosong pertama tanpa kotak dari vektor array kotak y. Frasa ini ditulis >@{.@(#~ #@>)dalam notasi diam-diam.

• Akhirnya, [: >@{.@(#~ #@>) allsbsqkumpulkan kalimat sebelumnya dengan allsbsqmenciptakan solusi untuk masalah yang kita miliki. Inilah frasa lengkap dengan spasi:

  [: >@{.@(#~ #@>) i.@# <@(~. #~ 1 = #/.~)@(]\) ]
  

Haskell, 135 Bytes

import Data.List
f ""=[""]
f g=map(snd)$head$groupBy(\a b->fst a==fst b)$sort[(length y,y)|[y]<-group$sort[x|x@(_:_)<-tails g>>=inits]]

PHP, 171 152 134 125

function f($s){while(!$a&&++$i<strlen($s))for($j=0;$b=substr($s,$j++,$i);)strpos($s,$b)==strrpos($s,$b)&&($a[]=$b);return$a;}

http://3v4l.org/RaWTN

Groovy (Java regex pada implementasi Oracle), 124

c={m=it=~/(?=(.*?)(?=(.*))(?<=^(?!.*\1(?!\2$)).*))/;o=m.collect({it[1]});o.findAll({it.size()==o.min({it.size()}).size()});}

Diuji pada Groovy 2.4 + Oracle JRE 1.7. Regex harus berfungsi untuk Java 6 hingga Java 8, karena bug yang memungkinkan kode di atas berfungsi tidak diperbaiki. Tidak yakin untuk versi sebelumnya, karena ada bug di Java 5 yang diperbaiki di Java 6.

Regex menemukan string terpendek yang tidak memiliki duplikat substring di tempat lain, di setiap posisi dalam string input. Kode di luar menangani penyaringan.

(?=(.*?)(?=(.*))(?<=^(?!.*\1(?!\2$)).*))

• Karena string dapat tumpang tindih, saya mengelilingi semuanya dengan pandangan ke depan (?=...).
• (.*?) mencari dari substring terpendek
• (?=(.*)) menangkap sisa string untuk menandai posisi saat ini.
• (?<=^(?!.*\1(?!\2$)).*)adalah emulasi dari variabel-panjang melihat-belakang, yang mengambil keuntungan dari bug implementasi yang memungkinkan (?<=.*)untuk melewati pemeriksaan panjang.

• (?!.*\1(?!\2$))cukup periksa bahwa Anda tidak dapat menemukan substring yang sama di tempat lain. Yang (?!\2$)menolak posisi asli di mana substring dicocokkan.

  Batas konstruk look-around luar tidak berlaku untuk konstruk look-around bersarang. Oleh karena itu, pandangan negatif di depan (?!.*\1(?!\2$))sebenarnya memeriksa seluruh string, bukan hanya sampai batas kanan tampilan di belakang.

Rebol, 136 byte

f: func[s][repeat n length? b: copy s[unless empty? x: collect[forall s[unless find next find b t: copy/part s n t[keep t]]][return x]]]

Tidak Terkumpul:

f: func [s] [
    repeat n length? b: copy s [
        unless empty? x: collect [
            forall s [
                unless find next find b t: copy/part s n t [keep t]
            ]
        ][return x]
    ]
]

Contoh penggunaan:

>> f ""       
== none

>> f "abcaa"
== ["b" "c"]

>> f "rererere"
== ["ererer"]

>> f "asdfasdfd"
== ["fa" "fd"]

>> f "ffffhhhhfffffhhhhhfffhhh"
== ["hffff" "fffff" "hhhhh" "hfffh"]

>> f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"
== ["fas" "fad" "add" "fds"]

NB. Saya kira inti dari kodenya adalah bagaimana findbagian ini bekerja. Semoga ini akan membantu menjelaskan ...

>> find "asdfasdfd" "df"
== "dfasdfd"

>> next find "asdfasdfd" "df"
== "fasdfd"

>> find next find "asdfasdfd" "df" "df"
== "dfd"

>> ;; so above shows that "df" is present more than once - so not unique
>> ;; whereas below returns NONE because "fa" found only once - ie. bingo!

>> find next find "asdfasdfd" "fa" "fa"
== none

Haskell, 119

f s=[r|n<-[1..length s],l<-[map(take n)$take(length s-n+1)$iterate(drop 1)s],r<-[[j|j<-l,[j]==[r|r<-l,r==j]]],r/=[]]!!0

Brachylog , 10 byte

sᶠ≡ᵍ~gˢlᵍt

Cobalah online!

sᶠ            The list of every substring of the input
  ≡ᵍ          grouped by identity,
    ~gˢ       with length-1 groups converted to their elements and other groups discarded,
       lᵍ     and grouped by their length,
         t    has the output as its last group.

Meskipun ᵍtidak secara alami mengurutkan berdasarkan nilai yang dikelompokkan, alih-alih memesan grup dengan kemunculan pertama dari setiap nilai, kejadian pertama dari setiap panjang berada dalam urutan menurun. Saya tidak 100% yakin bahwa pemfilteran keunikan tidak dapat mengacaukan ini, tetapi saya belum membuat test case ini gagal.

05AB1E , 10 byte

Œʒ¢}é.γg}н

Tidak menghasilkan apa pun untuk string kosong.

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

Π          # Get all substrings of the (implicit) input-String
 ʒ          # Filter it by:
  ¢         #  Count how many times the current substring occurs in the (implicit) input-String
            #  (only 1 is truthy in 05AB1E, so the filter will leave unique substrings)
   }é       # After the filter: sort the remaining substrings by length
     .γg}   # Then group them by length as well
         н  # And only leave the first group containing the shortest substrings
            # (which is output implicitly as result)

Ini mengambil keuntungan dari 05AB1E yang hanya memiliki 1nilai kebenaran, dan yang lainnya sebagai falsey. Substring unik terpendek selalu dijamin terjadi tepat sekali untuk semua string input yang mungkin. (Untuk string input yang hanya berisi karakter yang sama (yaitu aaaaa), string input itu sendiri sebagai substring terjadi sekali saja, jadi hasilnya adalah ["aaaaa"]. Untuk string input dengan pola berulang (yaitu "abcabc"), masih ada substring unik yang hanya terjadi sekali ( ["abca","abcab","abcabc","bca","bcab","bcabc","ca","cab","cabc"]), jadi ini akan menghasilkan ["ca"].)

Python 2, 150

import re
a=input()
r=range
l=len(a)
d=0
for i in r(l):
 if d:break
 for j in r(l-i):
  k=a[j:i+j+1]
  if len(re.findall("(?="+k+")",a))<2:d=1;print k

Perl 5 -a , 114 87 byte

map{//;(grep$' eq$_,@q)-1||($l||=y///c)-y///c||say}@q=map{"@F"=~/(?=(.{$_}))/g}1..y///c

Cobalah online!

Metode lama: 114 byte