Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » minimale Anzahl an cuts für eine String Überdeckung
Autor
Universität/Hochschule minimale Anzahl an cuts für eine String Überdeckung
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Themenstart: 2021-10-19

Hallo, Gegeben ist ein String s und eine liste von strings arr. Es soll die minimale Anzahl an cuts ausgegeben werden, so dass s wenn es an entsprechenden indizes geschnitten wird ganz und überschneidungsfrei von strings aus arr abgedeckt wird. Ein Beispiel: s = gattacagatc arr = ["gat", "gatta", "tac", "agatc"] Die minimale cut Zahl ist hier 3. Ich komme über eine Brute Force Lösung nicht hinaus, hat jemand eine Idee wie es schneller gehen kann?


   Profil
__blackjack__
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.09.2021
Mitteilungen: 81
  Beitrag No.1, eingetragen 2021-10-20

Wie sieht denn Deine Brute Force Lösung aus? Die kann man ja verschieden (in)effizient machen. Mein Bauchgefühl vermutet, dass das nicht ohne eine erschöpfende Suche des Suchraums geht.


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.2, vom Themenstarter, eingetragen 2021-10-20

Hi, Danke für deine Antwort. Ich habe mir noch ein paar Gedanken gemacht und bin auf folgenden Ansatz gekommen: Erst bilde ich einen Trie der aus den strings in arr besteht https://en.wikipedia.org/wiki/Trie ). Dann erzeuge ich ein Array dp der Länge des Strings s, gelte \(\mid s \mid = n\). Dann berechne ich für den string s[i...n] die minimale Anzahl an cuts das geht in \(O(k)\) wobei \(k\) die Länge des längsten Wortes in arr ist. Dabei ist i eine Laufvariable und läuft von \(n-1\) bis \(0\). Die anzahl minimaler cuts für den String s[i...n] speichere ich in dp[i]. So errechnet sich s[j...n] = s[i...n] + 1 für ein \(i > j\). Das ganze sollte in \(O(n \cdot k)\) laufen. Habe ich das richtig durchdacht?


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7273
Wohnort: Milchstraße
  Beitrag No.3, eingetragen 2021-10-20

Hallo, ich würde es rekursiv machen. Im ersten Schritt werden alle Wörter aus arr bestimmt, mit denen s anfangen kann. Im Beispiel sind das gat und gatta. Für jedes dieser Wörter muss dann das Restwort (im Beispiel tacagatc bzw. cagatc) abermals mit Wörtern aus arr zusammengebaut werden. Das ursprüngliche Problem wurde also auf ein kleineres analoges Problem zurückgeführt. Das sollte ziemlich flink gehen.


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.4, vom Themenstarter, eingetragen 2021-10-20

Hi, Es hängt davon ab wie du prüfen würdest, mit welchen wörtern der string anfangen kann oder? Außerdem, es kann vorkommen, dass du den für gleichen Reststring mehrmals berechnest wie viele cuts er minimal braucht, weil der Reststring auf verschiedene Art von Wörtern aus dem array abgedeckt werden kann.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7273
Wohnort: Milchstraße
  Beitrag No.5, eingetragen 2021-10-20

\quoteon(2021-10-20 11:37 - dvdlly in Beitrag No. 4) 1) Es hängt davon ab wie du prüfen würdest, mit welchen wörtern der string anfangen kann oder? 2) Außerdem, es kann vorkommen, dass du den für gleichen Reststring mehrmals berechnest wie viele cuts er minimal braucht, weil der Reststring auf verschiedene Art von Wörtern aus dem array abgedeckt werden kann. \quoteoff 1) Das ist doch ein Leichtes! Für jedes Wort aus arr fängst du vorne an und vergleichst Buchstabe für Buchstabe mit s. 2) Das kann wohl vorkommen (obwohl ich deinen Satz nicht ganz verstanden habe).


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.6, vom Themenstarter, eingetragen 2021-10-20

Kein Wunder, dass du den Satz nicht verstanden hast - ich hab mich verschrieben :P Wenn du aber z.B. arr = ["abca","abcb","abcc","abcd"] und s = "abcdabcd", dann ist die Laufzeit nicht so gut. Aber du hast Recht - so schlecht ist die Methode gar nicht, wie sie mir auf den ersten Blick schien.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7273
Wohnort: Milchstraße
  Beitrag No.7, eingetragen 2021-10-20

\quoteon(2021-10-20 12:34 - dvdlly in Beitrag No. 6) Wenn du aber z.B. arr = ["abca","abcb","abcc","abcd"] und s = "abcdabcd", dann ist die Laufzeit nicht so gut. \quoteoff Dieses Beispiel ist nicht so gut gewählt, wie ich finde. Denn es gibt nur ein einziges Anfangsstück aus arr, das zu s passt. Und daher ist die Laufzeit doch optimal! Problematisch könnte es werden, wenn in der Rekursion immer (oder oft) mehrere Anfangsstücke zur Auswahl stehen. Dann könnte evtl. exponentielle Laufzeit auftreten.


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
__blackjack__
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.09.2021
Mitteilungen: 81
  Beitrag No.8, eingetragen 2021-10-20

Man könnte sich auch überlegen für einmal gefundene (Teil)Lösungen einen Cache anzulegen. So dass man keine (Teil)Zeichenketten mehrfach zerlegt.


   Profil
dvdlly wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]