Kürzester Teilstring-Index

9

Ich bin eine faule, aber effiziente Person, wie viele von Ihnen wahrscheinlich auch. Wenn ich also etwas mache, möchte ich es mit minimalem Aufwand machen. Deshalb bitte ich Sie, dieses Problem für mich zu lösen.

Was ich hier habe, ist eine Art Dokument. In jeder Zeile dieses Dokuments befindet sich ein einzelnes Wort oder eine kurze Phrase. Das Dokument ist nicht sortiert, aber das ist in Ordnung. Ich weiß, wo alles ist. Ich könnte Hilfe gebrauchen, um Dinge schneller zu finden, und dafür brauche ich eine zweite Liste. Hier kommen Sie ins Spiel. Für jede Textzeile in diesem Dokument benötige ich eine Kennung. Etwas, das ich CTRL+ kann F, aber es kann nicht länger als unbedingt notwendig sein, um dieses eine Ergebnis zu erzielen.

Beispieleingabe:

(blank)
an apple
spiderman 3
7pm pick up laundry
tequila
fake mustache
dishes on wednesday
banana
biscuits
(blank)

Beispielausgabe:

ap,3,7,q,f,w,ba,bi

Ich werde mich hier wiederholen, um sicherzustellen, dass wir auf derselben Seite sind:

  • Die Eingabe ist eine unformatierte Textdatei mit einer Liste von Elementen, die durch Zeilenumbrüche getrennt sind. Ich habe es hier im TXT-Format, es heißt "STUFF.TXT"
  • Die erste und letzte Zeile des Dokuments sind leer. Jede zweite Zeile enthält einen Eintrag mit einer Länge> 0.
  • Die Datei enthält nur alfanumerische Zeichen (alle Kleinbuchstaben), Leerzeichen und Zeilenumbrüche.
  • Die gewünschte Ausgabe ist eine Liste von Bezeichnern in derselben Reihenfolge wie meine ursprüngliche Liste.
  • Ich möchte nicht mehr als ein Suchwort für jedes Listenelement. Wenn es mehrere Antworten gibt, wählen Sie eine aus, es ist mir egal, welche. Im obigen Beispiel habe ich 'ap' für ausgewählt an apple, aber Sie hätten auch 'n', 'a', 'pp', 'pl' oder 'le' auswählen können. Nicht 'ein', denn das ist drin banana.
  • Ich kann Ihnen versichern, dass die Datei niemals leer ist und niemals Duplikate enthält.
  • Bei Bedarf können Sie auf dem Leitungsabschluss übereinstimmen. Dies ist jedoch ein letzter Ausweg, der nur verwendet werden kann, wenn es keine andere Möglichkeit gibt, zwischen Listenelementen zu unterscheiden (z. B. "Apfel" und "Äpfel").

Standardlücken sind nicht erlaubt. Dies ist auch Code Golf, so dass der kürzeste Code gewinnt.

Noch ein Beispiel:

(blank)
ban
any
king
bean
yen
rake
raki
bar
(blank)

Und seine Ausgabe:

ban,ny,g,be,ye,ke,aki,ar
freekvd
quelle
1
@CarpetPython muss es so kurz wie möglich sein. Leerzeichen können in Eingabe und Ausgabe sein, das wurde der Frage hinzugefügt.
freekvd
Können wir auch Zeilenumbrüche am Anfang des Suchbegriffs verwenden, wenn eine Zeichenfolge ein Suffix einer anderen ist?
Martin Ender
@ MartinBüttner ja. Aus diesem Grund beginnt und endet das Dokument mit einer Leerzeile, sodass Sie diese Zeilenumbrüche am Anfang und Ende jedes Listenelements haben.
Freekvd
4
Ich bin mir ziemlich sicher, dass dieses Problem NP-vollständig ist. Ich denke, ich kann das genaue Deckungsproblem auf dieses reduzieren.
FUZxxl
4
Es ist mehr so, dass Sie keine kreativen Lösungen sehen, da es keine bessere Lösung als Brute Force gibt.
FUZxxl

Antworten:

3

Pyth, 39 Bytes

Lsm.:bdtUbKfT.zj\,mhf!}Yjb-Kk+yky++bkbK

Bruteforces alle Teilmengen jeder Zeichenfolge in zunehmender Länge und prüft, ob diese Zeichenfolge in einer anderen Zeichenfolge vorkommt. Wenn dies nicht funktioniert, wird es mit Ausnahme aller Teilmengen von dasselbe tun \nstring\n.

orlp
quelle
Ich erhalte einen schlechten Typkombinationsfehler, wenn ich dies teste. pyth.herokuapp.com/…
freekvd
@freekvd Heroku muss eine veraltete Version von Pyth haben, da das Aufrufen .:mit dem ersten Typ string und dem zweiten Typ int kein Fehler ist. Versuchen Sie es mit Pyth aus dem Repo: github.com/isaacg1/pyth
orlp