LongestCommonSubsequence - Start und Ende in den Strings

[srs.pas]

Hi!
Ich bin ganz neu hier! Bei meinen Recherchen im Web in der Hoffnung mein Problem zu lösen, bin ich auf dieses Portal gestossen. Bei dieser Gelegenheit möcht Ich euch mein Problem schildern. Vielleicht kann mir der ein oder andere ja helfen
Ich bedanke mich jedenfalls für jede Hilfe im Vorraus.

Also: Ich beschäftige mich gerade mit LCS (Longest common subsequence) zu Deutsch, Längste gemeinsame Teilkette.
Bsp.
abcdefg ---- adeb
de - wäre hier somit die LCS

Im speziellen beschäftige ich mich noch mit dem Laufzeitverhalten und optimierungsmethoden im LCS bereich.
Die LCS ist ja eine bekannte Problemstellung und es gibt unzählige Algorithmen dafür.
Mir ist folgender Rekursiver Algorithmus realtiv sympatisch (das er nicht das non plus Ultra ist, ist mir bewusst)

Funktionieren tut das so wie es soll, ich versteh das ding allerdings nicht zu 100%.
Mein Wunsch wäre in der Function LCS noch den Anfang der berechneten Teilkette sowie das Ende der Teilkette von beiden Strings zu berechnen.
Also zb.
s1 = abcdefg
s2 = bcdfg
LCS = bcd
s1 LCS anfang = 3
s1 LCS ende = 5
s2 LCS anfang = 1
s2 LCS ende = 3

Ich weiß nicht wie und wo ich für dieses Problem ansetzten soll.
Ich bin für jede Hilfe dankbar! Vll. ist es ja auch völlig Trivial und ich pack es nur nicht weil ich den Algo. nicht zu 100% versteh.

Code: Alles auswählen

Program LongestCommonSubsequence(output);
 
function lcs(a, b: string): string;
  var
    x, y: string;
    lenga, lengb: integer;
  begin
    lenga := length(a);
    lengb := length(b);
    lcs := '';
    if (lenga >  0) and (lengb >  0) then
      if a[lenga] =  b[lengb] then
        lcs := lcs(copy(a, 1, lenga-1), copy(b, 1, lengb-1)) + a[lenga]
      else
      begin
        x := lcs(a, copy(b, 1, lengb-1));
        y := lcs(copy(a, 1, lenga-1), b);
        if length(x) > length(y) then
          lcs := x
        else
          lcs := y;
      end;
  end;
 
var
  s1, s2: string;
begin
  s1 := 'thisisatest';
  s2 := 'testing123testing';
  writeln (lcs(s1, s2));
  s1 := '1234';
  s2 := '1224533324';
  writeln (lcs(s1, s2));
end.

[theo]

Ich glaube du hast die Funktionsweise nicht ganz kapiert.

Du hast das ja von hier kopiert: http://rosettacode.org/wiki/Longest_com ... nce#Pascal

Dort steht oben wie es geht: http://rosettacode.org/wiki/Longest_common_subsequence

Das Resultat setzt sich ja aus allen Teilstrings zusammen. Also welche Position willst du haben?

[srs.pas]

Ja richtig die Quelle stimmt, aber ich möchte festhalten das ich diesen Algorithmus nicht als meinen verkauft habe

Wie oben beschrieben ich würde gerne die Position der LCS in beiden Strings wissen also wo die LCS im String beginnt.

[Michl]

Das Einfachste wäre es dann wohl, die Positionen der Teilstrings im Nachhinein zu bestimmen. Pos und Length (bzw deren UTF8-Adäquate) wären dafür geeignet.