Finden Sie Muster in Strings

17

In dieser Herausforderung besteht Ihre Aufgabe darin, Teilzeichenfolgen mit einer bestimmten Struktur zu lokalisieren.

Eingang

Ihre Eingabe besteht aus zwei nicht leeren alphanumerischen Zeichenfolgen, einem Muster p und einem Text t . Die Idee ist, dass jedes Zeichen von peine zusammenhängende nicht leere Teilzeichenfolge darstellt, tdie nebeneinander auftritt, und pderen Verkettung darstellt. Identische Zeichen entsprechen identischen Teilzeichenfolgen. Das Muster aastellt beispielsweise ein beliebiges nicht leeres Quadrat dar (eine Zeichenfolge, die durch Verketten einer kürzeren Zeichenfolge mit sich selbst erhalten wird). Somit kann das Muster bei jeder Übereinstimmung mit aader Teilzeichenfolge übereinstimmen .byebyeabye

Ausgabe

Wenn der Text teine pübereinstimmende :Teilzeichenfolge enthält , ist Ihre Ausgabe diese Teilzeichenfolge, wobei Doppelpunkte zwischen die Zeichenfolgen eingefügt werden, die den Zeichen von entsprechen p. Zum Beispiel, wenn wir haben t = byebyenowund p = aadann bye:byeeine akzeptable Ausgabe. Es kann mehrere Möglichkeiten für den passenden Teilstring geben, Sie sollen jedoch nur eine davon ausgeben.

Wenn tkeine passende Teilzeichenfolge enthalten ist, ist Ihre Ausgabe ein trauriges Gesicht :(.

Regeln und Erläuterungen

Verschiedene Zeichen von pkönnen identischen Teilzeichenfolgen entsprechen, sodass p = abasie mit der Zeichenfolge übereinstimmen können AAA. Beachten Sie, dass die Zeichen nicht leeren Zeichenfolgen entsprechen müssen. Insbesondere wenn plänger als ist t, muss die Ausgabe sein :(.

Sie können ein vollständiges Programm oder eine Funktion schreiben und die Reihenfolge der beiden Eingänge ändern. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Testfälle

Im Format angegeben pattern text -> output. Beachten Sie, dass möglicherweise andere zulässige Ausgaben vorhanden sind.

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
quelle
1
Das Powerset aller Teilstrings? Warum nicht!
Orlp
1
@orlp Es ist nur O(2^((n * (n + 1))/2)): P
ThreeFx
Was bedeutet eine Ziffer in der Musterfolge?
Feersum
@feersum Es ist ein Zeichen, es ist also im Wesentlichen dasselbe wie jedes andere Zeichen.
ThreeFx
@ThreeFx Ich bin mir nicht sicher, weil der erste Absatz sich nur auf "Buchstaben" im Muster bezieht.
Feersum

Antworten:

6

Python, 207 Bytes

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

Mit anrufen g(pattern, string)

Verwendet das reModul, um den größten Teil der Arbeit zu erledigen.

Die Nummer eins
quelle
1

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

Seit der Veröffentlichung von ES6 im Juni 2015 veröffentliche ich die ES5.1-Version des Codes zusammen mit der ES6-Entsprechung, deklariere jedoch die ES5.1-Version als Hauptantwort.

Gierige Übereinstimmung, daher gibt der erste Fall "Nicht" anstelle von "N" zurück.

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

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

Probieren Sie es online!

Übernimmt die Argumente in der Currying-Syntax: f(a)(b)

Erklärung (und 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
quelle
1

Brachylog , 35 Bytes

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

Probieren Sie es online!

Bei nicht ganz kleinen Eingängen sehr langsam. Ich habe den sechsten Testfall nicht wirklich durchgeführt, aber nicht, weil ich es nicht ausprobiert habe, langsam. (Möglicherweise, weil jede Partition jedes Teilstrings brachial erzwungen wurde, beginnend mit der größten, und dann überprüft wurde, ob eine Übereinstimmung vorliegt.) Nimmt die Eingabe als Liste [pattern,string].

Verkürzte und geteilte Erklärung:

sᵗ~cᵗX

X ist das Muster, das mit einer Partition eines Teilstrings der Eingabezeichenfolge gepaart ist.

lᵛ

Das Muster und die Partition haben die gleiche Anzahl von Elementen.

Xzdz≠ʰ

Keine zwei eindeutigen pattern char, matched substringPaare teilen ein Musterzeichen. Das heißt, kein Musterzeichen wird mehreren Teilzeichenfolgen zugeordnet, obwohl mehrere Musterzeichen einer Teilzeichenfolge zugeordnet werden können.

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

Die Ausgabe besteht aus den Elementen der Partition, die durch Doppelpunkte verbunden sind, es sei denn, etwas konnte nicht getan werden. In diesem Fall ist dies :(stattdessen der Fall .

Monolithische Erklärung:

                                       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
                               ":("    ":(".
Nicht verwandte Zeichenfolge
quelle
Es ist mehr als eine Stunde vergangen und der sechste Testfall ist noch nicht abgeschlossen ... Vielleicht funktioniert es tatsächlich nicht? Es verbraucht mehr als der Anteil des Prozessors ...
Unrelated String
Okay, entweder habe ich die zeitliche Komplexität der Verwendung mehrerer Schichten harter Brute Force unterschätzt, oder dies ist in gewisser Weise kaputt, weil es immer noch nicht den sechsten Testfall durchgeführt hat
Unrelated String
Ich habe es jetzt heruntergefahren, weil ich nicht sicher bin, wie lange ich noch warten kann, wenn es drei Stunden dauert
Unrelated String