Grössten gemeinsamen Teilstring aus 2 Strings?

[Biesterfeld]

Hej,

da es dazu offensichtlich noch keine konkrete Antwort gab, möchte ich ganz kurz ein bekanntes Prinzip aus der Bioinformatik vorstellen. Dieses Problem ist allerdings in sofern noch komplexer, als dass auch Lücken zwischen den Teilstrings zugelassen werden. Von dieser Problemstellung aus, ist folgende Vorgehensweise sinnvoll, ob sie aber u.U. für obiges Problem nicht zu aufwendig ist, kann ich schlecht abschätzen.

Was gemacht wird, ist dass beide Strings in einer binären Matrix (einem sog. Dotplot) repräsentiert werden, um ihre Ähnlichkeit darzustellen.

Bsp.: String 1 Autobahnplanke
      String 2 Kaffeeautomat

A u t o b a h n p l a n k e
               K                         *
               a *         *         *
               f
               f
               e                           *
               e                           *
               a *          *        *
               u   *
               t     *
               o       *
               m
               a *          *        *
               t      *

Was nun nur noch getan werden muss, ist die Matrix nach existierenden  Diagonalen auszuwerten. Um den Aufwand zu reduzieren empfiehlt es sich eine minimale Vorgabe zu machen (z.b. soll der String mindestens 3 Zeichen enthalten)und Abbruchbedingungen einzuführen:
  Der längste bisher gefunde String ist 5 Zeichen lang
  Wenn Restdiagonalenlänge kleiner 5 brich ab!

Wenn man auf die graphische Repräsentierung verzichtet kann man sich natürlich den Schritt über die Matrix sparen, sich aber das Vorgehen dennoch anhand derer veranschaulichen. Das Problem ist O(nm)-komplex.

Beste Grüße
Biesterfeld