Laufzeit Algorithmus: Vergleich von Strings |
| 13.02.2016, 16:49 | Sandra1212 | Auf diesen Beitrag antworten » |
| Laufzeit Algorithmus: Vergleich von Strings Hallo, mein Problem ist das folgende: Ich habe zwei beliebig lange Strings und möchte wissen, ob die beiden sich "überlappen", d.h. ob ein beliebig langes Suffix des ersten Strings gleich einem beliebig langen Präfix des zweiten Strings ist. Beispiel: ABC und BCAB überlappen sich A und AB überlappen sich ABC und AB überlappen sich wegen der Reihenfolge nicht (AB und ABC aber schon) In welcher Laufzeit ist das möglich? Meine Ideen: Zuerst müssen die beiden Strings ja gelesen werden. Angenommen, einer ist n, der andere m lang. Das führt zu O(n+m). Ich weiß aber nicht, wie ich die einzelnen Zeichen jetzt am besten vergleichen könnte... |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
