Znajdź wzory w ciągach znaków

17

W tym wyzwaniu Twoim zadaniem jest zlokalizowanie podciągów o określonej strukturze.

Wejście

Twoje dane powinny składać się z dwóch niepustych ciągów alfanumerycznych, wzorca p i tekstu t . Chodzi o to, że każdy znak preprezentuje ciągłe niepuste podciągi, tktóre występują obok siebie, i preprezentuje ich konkatenację. Identyczne znaki odpowiadają identycznym podciągom; na przykład wzór aareprezentuje dowolny niepusty kwadrat (ciąg uzyskany przez połączenie krótszego ciągu z samym sobą). W ten sposób wzór aamoże dopasować podciąg byebye, z każdym adopasowaniem bye.

Wynik

Jeśli tekst tzawiera podłańcuch, który ppasuje, wówczas wynikiem będzie podłańcuch z dwukropkami :wstawionymi między ciągi znaków odpowiadające znakom p. Na przykład, jeśli mamy t = byebyenowi p = aa, to bye:byejest akceptowalny wynik. Może istnieć kilka opcji dopasowania podłańcucha, ale wypisujesz tylko jedną z nich.

Jeśli tnie zawiera pasującego podciągu, twoja praca będzie smutną miną :(.

Zasady i wyjaśnienia

Różne znaki pmogą odpowiadać identycznym podciągom, więc p = abamogą pasować do łańcucha AAA. Zauważ, że znaki muszą odpowiadać niepustym ciągom; w szczególności, jeśli pjest dłuższy niż t, wyjście musi być :(.

Możesz napisać pełny program lub funkcję, a także zmienić kolejność dwóch wejść. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

Podany w formacie pattern text -> output. Zauważ, że mogą istnieć inne dopuszczalne wyniki.

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
źródło
1
Powerset wszystkich podciągów? Dlaczego nie!
orlp
1
@orlp To tylko O(2^((n * (n + 1))/2)): P
ThreeFx
Co oznacza cyfra w ciągu wzorca?
feersum
@feersum Jest to postać, więc zasadniczo jest taka sama jak każda inna postać.
ThreeFx
@ThreeFx Nie jestem pewien, ponieważ pierwszy akapit odnosi się tylko do „liter” we wzorze.
feersum

Odpowiedzi:

6

Python, 207 bajtów

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":("

Zadzwoń z g(pattern, string)

Wykorzystuje remoduł do wykonywania większości prac.

Numer jeden
źródło
1

JavaScript (SpiderMonkey) (ES5.1), 198 bajtów

Ponieważ ES6 został wydany w czerwcu 2015 r., Publikuję wersję kodu ES5.1 wraz z odpowiednikiem ES6, ale deklaruję wersję ES5.1 jako główną odpowiedź.

Chciwy mecz, więc pierwszy przypadek zwraca „Nie” zamiast „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(":"):":("}

Wypróbuj online!

JavaScript (Node.js) (ES6), 141 bajtów

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`:`:":("

Wypróbuj online!

Bierze argumenty w składni curry: f(a)(b)

Objaśnienie (i bez golfa):

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
źródło
1

Brachylog , 35 bajtów

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

Wypróbuj online!

On nie całkiem małych nakładów, bardzo wolno. W rzeczywistości nie zrobiłem powolnego szóstego przypadku testowego, ale nie z powodu braku prób. (Prawdopodobnie z powodu brutalnego wymuszania każdej partycji każdego podłańcucha, zaczynając od największego, a następnie sprawdzając, czy jest on zgodny.) Pobiera dane wejściowe jako listę [pattern,string].

Skrócone i podzielone wyjaśnienie:

sᵗ~cᵗX

X jest wzorcem sparowanym z partycją podłańcucha ciągu wejściowego.

lᵛ

Wzór i partycja mają tę samą liczbę elementów.

Xzdz≠ʰ

Żadne dwie unikalne pattern char, matched substringpary nie mają wspólnego wzoru. Oznacza to, że żaden znak wzorca nie jest odwzorowywany na wiele podciągów, chociaż wiele znaków wzorca może być odwzorowywanych na jeden podciąg.

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

Dane wyjściowe to elementy partycji połączone dwukropkami, chyba że nic nie można zrobić, w takim przypadku tak jest :( zamiast tego.

Objaśnienie monolityczne:

                                       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
                               ":("    ":(".
Niepowiązany ciąg
źródło
Minęła ponad godzina i nadal nie udało się zrobić szóstego przypadku testowego ... może to naprawdę nie działa? Zużywa więcej niż swój udział w procesorze ...
Niepowiązany ciąg
Okej, albo nie doceniłem złożoności czasowej użycia wielu warstw twardej brutalnej siły, albo to jest w jakiś sposób zepsute, ponieważ wciąż nie wykonałem szóstego przypadku testowego
Niepowiązany ciąg
Zamknąłem go teraz, ponieważ jeśli zajmie to trzy godziny, nie jestem pewien, jak długo jestem jeszcze gotów czekać
Niepowiązany ciąg