Kürzeste, eindeutig identifizierende Teilzeichenfolgen

23

Ersetzen Sie bei einer vorgegebenen Liste von Zeichenfolgen jede Zeichenfolge durch eine ihrer nicht leeren Teilzeichenfolgen, die keine Teilzeichenfolge der anderen Zeichenfolgen in der Liste ist und so kurz wie möglich ist.

Beispiel

In Anbetracht der Liste ["hello","hallo","hola"], "hello"sollte nur ersetzt werden , "e"da diese Teilzeichen nicht enthalten ist in "hallo"und "hola"und es ist so kurz wie möglich. "hallo"ersetzt werden könnte durch entweder "ha"oder "al"und "hola"durch irgendeine "ho", "ol"oder "la".

Regeln

  • Sie können davon ausgehen, dass die Zeichenfolgen nicht leer sind und nur alphabetische Zeichen derselben Groß- / Kleinschreibung enthalten.
  • Sie können davon ausgehen, dass für jede Zeichenfolge in der Liste eine solche Teilzeichenfolge vorhanden ist, dh, keine Zeichenfolge in der Liste ist eine Teilzeichenfolge einer der anderen Zeichenfolgen.
  • Eingabe und Ausgabe können in jedem vernünftigen Format erfolgen.
  • Das ist , also versuchen Sie, so wenig Bytes wie möglich in der Sprache Ihrer Wahl zu verwenden.

Testfälle

In den meisten Fällen wird nur eine mögliche Ausgabe angegeben.

["ppcg"] -> ["p"] (or ["c"] or ["g"])
["hello","hallo","hola"] -> ["e","ha","ho"]
["abc","bca","bac"] -> ["ab","ca","ba"]
["abc","abd","dbc"] -> ["abc","bd","db"]
["lorem","ipsum","dolor","sit","amet"] -> ["re","p","d","si","a"]
["abc","acb","bac","bca","cab","cba"] -> ["abc","acb","bac","bca","cab","cba"]

Verwandte Themen : Kürzeste identifizierende Teilzeichenfolge - ähnliche Idee, aber komplexere Regeln und umständliches Format.

Laikoni
quelle
Warum ist nicht ""(leere Zeichenfolge) eindeutig für den Einzelfall zu identifizieren "ppcg"?
MooseBoys
2
@MooseBoys Wenn Sie eine Liste mit Zeichenfolgen haben, ersetzen Sie jede Zeichenfolge durch eine der nicht leeren Teilzeichenfolgen
Mr. Xcoder,

Antworten:

4

Python 2 , 116 Bytes

def f(a):g=lambda s,S:s not in`set(a)-{S}`[3:]and min(s,g(s[1:],S),g(s[:-1],S),key=len)or S;return[g(s,s)for s in a]

Probieren Sie es online!

Chas Brown
quelle
4

Pyth , 12 Bytes

mhf!ts}LTQ.:

Probieren Sie es hier aus!

Wie es funktioniert

Grundsätzlich werden die Teilzeichenfolgen der einzelnen Zeichenfolgen gefiltert, die nur in einer der Zeichenfolgen in der Liste vorkommen (d. H., Diese Zeichenfolge ist eindeutig), und die erste wird abgerufen.

mhf!ts}LTQ.:     Full program, Q=eval(stdin_input())
m         .:     Map over Q and obtain all the substrings of each.
  f              And filter-keep those that satisfy (var: T)...
      }LTQ       ... For each string in Q, yield 1 if it contains T, else 0.
   !ts           ... Sum the list, decrement and negate. 
 h               Head. Yields the first valid substring, which is always the shortest.
Mr. Xcoder
quelle
4

Prolog (SWI) , 175 163 Bytes

S/L/R:-sub_string(S,_,L,_,R).
[H|T]+[I|R]:-string_length(H,L),between(1,L,X),H/X/I,T+R.
R+R.
L-R:-L+R,forall(member(E,L),findall(_,(member(F,R),\+ \+ E/_/F),[_])).

Probieren Sie es online!

Die meisten Dinge hier sollten ziemlich offensichtlich sein, aber:

Erläuterung

Signaturen: ( += Eingabe, ?= optional, -= Ausgabe, := Ausdruck)

  • sub_string(+String, ?Before, ?Length, ?After, ?SubString)
  • string_length(+String, -Length)
  • member(?Elem, ?List)
  • between(+Low, +High, ?Value)
  • findall(+Template, :Goal, -Bag)
  • forall(:Cond, :Action)

\+ \+is just not not(dh konvertiert eine Übereinstimmung in einen Booleschen Wert (in diesem Fall wird verhindert, dass beide ps ppcggetrennt übereinstimmen )

Nur ASCII
quelle
Das richtige Werkzeug für den Job: P mit Ausnahme der Tatsache, dass es umwerfend wortreich ist
ASCII
4

J , 30 29 25 Byte

1(|:(0{-.&,)"_1]\.)<\\.&>

Probieren Sie es online!

                   <\\.&>        a 3-dimensional array of substrings
1 |:                             transpose each matrix to sort the substrings by length
1              ]\.               all choices where one word is missing
    (0{-.&,)"_1                  for every matrix, flatten, remove substrings
                                  that are present in the corresponding complement,
                                  pick first
FrownyFrog
quelle
3

JavaScript (ES6), 93 Byte

a=>a.map(s=>(L=s.length,g=n=>a.every(S=>S==s|!~S.search(u=s.substr(n%L,n/L+1)))?u:g(n+1))(0))

Probieren Sie es online!

Wie?

Für jede Saite s der Länge L in dem Eingangsfeld a [] und beginnend mit n = 0 , verwenden wir die rekursive Funktion g () alle Teilketten zu erzeugen , u von s mit:

u = s.substr(n % L, n / L + 1)

Zum Beispiel mit s = "abc" und L = 3 :

 n | n%L | floor(n/L+1) | u
---+-----+--------------+-------
 0 |  0  |       1      | "a"
 1 |  1  |       1      | "b"
 2 |  2  |       1      | "c"
 3 |  0  |       2      | "ab"
 4 |  1  |       2      | "bc"
 5 |  2  |       2      | "c"
 6 |  0  |       3      | "abc"
 7 |  1  |       3      | "bc"
 8 |  2  |       3      | "c"

Einige Teilzeichenfolgen werden mehrmals generiert, aber das spielt keine Rolle. Wichtig ist, dass alle Teilzeichenfolgen der Länge N vor allen Teilzeichenfolgen der Länge N + 1 generiert wurden .

Wir stoppen den Prozess, sobald u in keinem anderen String S in a [] gefunden wird. Dies ist garantiert, wenn u == s im schlimmsten Fall gemäß der Herausforderungsregel # 2 ist:

Keine Zeichenfolge in der Liste ist eine Teilzeichenfolge einer der anderen Zeichenfolgen

Daher werden in dem obigen Beispiel die Schritte 7 und 8 tatsächlich niemals verarbeitet.

Arnauld
quelle
2

PowerShell , 107 Byte

($a=$args)|%{$(for($i=0;$i++-lt($g=($s=$_)|% Le*)){0..($g-$i)|%{$s|% s*g $_ $i}|?{!($a-match$_-ne$s)}})[0]}

Probieren Sie es online!

Erläuterung

Für jede angegebene Zeichenfolge (und weisen Sie das gesamte Array zu $a):

  • forFühren Sie eine Schleife über jede Teilzeichenfolgenlänge (1 basierend) der Zeichenfolge aus (indem Sie die Zeichenfolge selbst $sund die Länge der Zeichenfolge zuweisen $g).
  • Für jede Länge ( $i):
    • Erstellen Sie $ifür jeden Index eine Indexschleife von 0 bis Länge - :
      • Ruft den Teilstring des aktuellen Strings ( $s) an Position $_(Index) und Länge ab$i
      • Übergeben Sie diesen Teilstring an Where-Object( ?) und geben Sie ihn zurück, wenn:
        • Die Teilmenge von array ( $a), die die aktuelle Zeichenfolge nicht enthält $s, hat keine Übereinstimmung mit der aktuellen Teilzeichenfolge$_

Zurück auf der Zeichenfolgeebene haben wir alle Teilzeichenfolgen dieser Zeichenfolge, die in den anderen nicht gefunden wurden. Nehmen Sie also die erste, [0]da wir nur eine von ihnen benötigen, und fahren Sie mit der nächsten Zeichenfolge fort.

Briantist
quelle
0

C # (Visual C # Interactive Compiler) , 149 Byte

a=>a.Select(s=>{var t=s;for(int j=0,k,l=s.Length;j++<l;)for(k=-1;j+k++<l;)if(!a.Where(u=>s!=u&u.Contains(t=s.Substring(k,j))).Any())j=k=l;return t;})

Probieren Sie es online!

Weniger golfen ...

// a is an input array of strings
a=>
  // iterate over input array   
  a.Select(s=>{
    // t is the result string
    var t=s;
    // j is the substring length
    for(int j=0,k,l=s.Length;j++<l;)
      // k is the start index
      for(k=-1;j+k++<l;)
        // LINQ query to check if substring is valid
        // the tested string is collected in t
        if(!a.Where(u=>s!=u&u.Contains(t=s.Substring(k,j))).Any())
          // break loops
          j=k=l;
    // return result
    return t;
  })
Dana
quelle