Temukan Pola di Strings

17

Dalam tantangan ini, tugas Anda adalah menemukan substring dengan struktur yang diberikan.

Memasukkan

Input Anda harus berupa dua string alfanumerik yang tidak kosong, pola p dan teks t . Idenya adalah bahwa masing-masing karakter pmewakili substring non-kosong yang berdekatan tyang terjadi di samping satu sama lain, dan pmewakili penggabungan mereka. Karakter identik sesuai dengan substring identik; misalnya, polanya aamewakili sembarang kotak kosong (string yang diperoleh dengan menggabungkan string yang lebih pendek ke dirinya sendiri). Dengan demikian polanya aadapat cocok dengan substring byebye, dengan setiap apencocokan bye.

Keluaran

Jika teks tberisi substring yang pcocok, maka output Anda harus substring itu, dengan titik dua :dimasukkan di antara string yang sesuai dengan karakter p. Sebagai contoh, jika kita memiliki t = byebyenowdan p = aa, maka bye:byemerupakan output yang dapat diterima. Mungkin ada beberapa pilihan untuk substring yang cocok, tetapi Anda hanya akan menghasilkan salah satunya.

Jika ttidak mengandung substring yang cocok, output Anda akan menjadi wajah sedih :(.

Aturan dan Klarifikasi

Karakter yang berbeda pdapat sesuai dengan substring yang identik, sehingga p = abadapat cocok dengan string AAA. Perhatikan bahwa karakter harus sesuai dengan string yang tidak kosong; khususnya, jika plebih lama dari t, output harus :(.

Anda dapat menulis program atau fungsi lengkap, dan Anda juga dapat mengubah urutan kedua input. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Uji Kasus

Diberikan dalam format pattern text -> output. Perhatikan bahwa output lain yang dapat diterima mungkin ada.

a Not -> N
aa Not -> :(
abcd Not -> :(
aaa rerere -> re:re:re
xx ABAAAB -> A:A
MMM ABABBAABBAABBA -> ABBA:ABBA:ABBA
x33x 10100110011001 -> 10:1001:1001:10
abcacb 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> c:a0aa:0c:c:0c:a0aa
abccab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> a:a:0c0:0c0:a:a
abcbcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> :(
abcbdcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> 00:c:ca0aa0c:c:0:ca0aa0c:00:c
Zgarb
sumber
1
The powerset dari semua substring? Kenapa tidak!
orlp
1
@orlp Ini hanya O(2^((n * (n + 1))/2)): P
ThreeFx
Apa arti angka dalam string pola?
feersum
@feersum Ini adalah karakter, jadi pada dasarnya sama dengan karakter lainnya.
ThreeFx
@ThreeFx Saya tidak yakin karena paragraf pertama hanya merujuk ke "huruf" dalam pola.
feersum

Jawaban:

6

Python, 207 byte

import re
h=lambda x:"a"+str(ord(x))
def g(a,b):
 c,d="",set()
 for e in a:
  c+=["(?P<"+h(e)+">.+)","(?P="+h(e)+")"][e in d]
  d.add(e)
 f=re.search(c,b)
 return f and":".join(f.group(h(e))for e in a)or":("

Telepon dengan g(pattern, string)

Menggunakan remodul untuk melakukan sebagian besar pekerjaan.

TheNumberOne
sumber
1

JavaScript (SpiderMonkey) (ES5.1), 198 byte

Sejak ES6 dirilis pada Juni 2015, saya memposting versi ES5.1 kode bersama dengan ES6 yang setara, tetapi menyatakan versi ES5.1 sebagai jawaban utama.

Pertandingan serakah, jadi case pertama mengembalikan "Tidak", bukan "N".

function(a,b){c=[o="indexOf"];r=a.split("");return(m=RegExp(r.map(function(i){return(e=c[o](i))>0?"\\"+e:(c.push(i),"(.+)")}).join("")).exec(b))?r.map(function(x){return m[c[o](x)]}).join(":"):":("}

Cobalah online!

JavaScript (Node.js) (ES6), 141 byte

a=>b=>(c=[o="indexOf"],r=[...a],m=RegExp(r.map(i=>(e=c[o](i))>0?"\\"+e:(c.push(i),"(.+)")).join``).exec(b))?r.map(x=>m[c[o](x)]).join`:`:":("

Cobalah online!

Mengambil argumen dalam sintaks currying: f(a)(b)

Penjelasan (dan ungolfed):

function matchPattern(a, b) {                   // Main function
 var c = ["indexOf"];                           // Array used for the capturing groups
 var r = [...a];                                // Split the pattern first
 var m = RegExp(r.map(function(i) {             // Create the regex
  var e = c.indexOf(i);                         // Check if the character is found before
  if (e > 0)                                    // If so
   return "\\" + e;                             // Append the back reference to the regex
  else {                                        // If not
   c.push(i);                                   // Append the character to the array
   return "(.+)";                               // Append a capturing group to the regex
  }             
 }).join("")).exec(b);                          // Execute the regex
 if (m != null)                                 // If the pattern matches the string
  return r.map(function(x) {                    // Replace each letter
   return m[c.indexOf(x)];                      // With the corresponding substring
  }).join(":");                                 // And join them with ":"
 else                                           // If there is no match
  return ":(";                                  // Return ":("
}
Shieru Asakoto
sumber
1

Brachylog , 35 byte

sᵗ~cᵗXlᵛ∧Xzdz≠ʰ∧Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("

Cobalah online!

Pada input yang tidak terlalu kecil, sangat lambat. Saya-belum-benar-benar melakukan-ke-6-ujian-kasus-tetapi-bukan-karena-kurang-mencoba-lambat. (Mungkin karena memaksa setiap partisi dari setiap substring, mulai dengan yang terbesar, dan kemudian memeriksa apakah itu cocok.) Mengambil input sebagai daftar [pattern,string].

Penjelasan ringkas dan dibagi:

sᵗ~cᵗX

X adalah pola yang dipasangkan dengan partisi dari substring dari string input.

lᵛ

Pola dan partisi memiliki jumlah elemen yang sama.

Xzdz≠ʰ

Tidak ada dua pattern char, matched substringpasangan unik yang berbagi karakter pola. Artinya, tidak ada karakter pola yang memetakan ke beberapa substring, meskipun beberapa karakter pola dapat memetakan ke satu substring.

Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("

Outputnya adalah elemen-elemen dari partisi yang bergabung dengan titik dua, kecuali sesuatu tidak dapat dilakukan, dalam hal ini :( sebaliknya.

Penjelasan monolitik:

                                       The input
 ᵗ  ᵗ                                  with its last element replaced with
  ~c                                   a list which concatenates to
s                                      a substring of it
     X                                 is X,
       ᵛ                               the elements of which all have the same
      l                                length.
        ∧                              And,
         X                             X
          z                            zipped
           d                           with duplicate pairs removed
            z                          and zipped back
              ʰ                        has a first element
             ≠                         with no duplicate values.
               ∧                       Furthermore,
                 t                     the last element of
                X                      X
                  ~ṇ                   with its elements joined by newlines
                    {      }ᵐ          where each character of the joined string
                     Ḷ                 is a newline
                      ∧                and
                          |            is replaced with
                       ":"             a colon
                          |            or is passed through unchanged
                             .         is the output.
                              ∨        If doing any part of that is impossible,
                                       the output is
                               ":("    ":(".
String yang tidak terkait
sumber
Sudah lebih dari satu jam dan masih belum melakukan uji kasus keenam ... mungkin itu sebenarnya tidak berhasil? Ini menggunakan lebih dari bagian prosesornya ...
Unrelated String
Oke, baik saya meremehkan kompleksitas waktu menggunakan beberapa lapis kekuatan kasar, atau ini rusak dalam beberapa cara, karena masih belum melakukan uji kasus keenam
Unrelated String
Saya sudah mematikannya sekarang karena jika butuh tiga jam saya tidak yakin berapa lama lagi saya bersedia menunggu
String yang tidak terkait