Hallo,

ich habe da eine Aufgabe, wo man die längste/größte gemeinsame Subsequence herausfinden soll und es ist eigentlich eine beschreibende Methode, um das zu schaffen, doch blicke ich da nicht ganz durch. Also, warum z.b. die rot-markierten Kästchen jetzt rot markiert sind... stimmt das ganze überhaupt? Und wo "sieht" man da dann die Lösung?

Also, warum z.b. die rot-markierten Kästchen jetzt rot markiert sind

Das sind die Übereinstimmungen die einen Teil der LCS (Longest common subsequence) darstellen.

stimmt das ganze überhaupt?

Ja. Auf der Wikipedia-Seite (s.u.) gibts auch einen Pseudocode mit dem du das nachstellen kannst :

The function below takes as input sequences X[1..m] and Y[1..n] computes the LCS between X[1..i] and Y[1..j] for all 1 ≤ i ≤ m and 1 ≤ j ≤ n, and stores it in C[i,j]. C[m,n] will contain the length of the LCS of X and Y.

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13

function  LCSLength(X[1..m], Y[1..n])     C = array(0..m, 0..n)     for i := 0..m        C[i,0] = 0     for j := 0..n        C[0,j] = 0     for i := 1..m         for j := 1..n             if X[i] = Y[j]                 C[i,j] := C[i-1,j-1] + 1             else:                 C[i,j] := max(C[i,j-1], C[i-1,j])     return C[m,n]

Und wo "sieht" man da dann die Lösung?

In deinem Beispiel steht die Lösung ja schon drüber:
CGATAATTGAGA
GTTCCTAATA

Ansonsten würde ich vorschlagen du liest dich hier mal schlau:
http://en.wikipedia.org/wiki/Longest...quence_problem

Ich hab mal schnell etwas in C# gekritzelt um die LCS zu finden, eventuell hilft es dir ja:

Code csharp:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

using System;   namespace LCS {     class Program     {         static void Main(string[] args)         {             string word1 = "CGATAATTGAGA";             string word2 = "GTTCCTAATA";                         Console.WriteLine(lcsBack(word1, word2));             Console.ReadKey();         }           public static string lcsBack(string a, string b)         {             string aSub = a.Substring(0, (a.Length - 1 < 0) ? 0 : a.Length - 1);             string bSub = b.Substring(0, (b.Length - 1 < 0) ? 0 : b.Length - 1);                         if (a.Length == 0 || b.Length == 0)                             return "";                         else if(a[a.Length - 1] == b[b.Length -1])                             return lcsBack(aSub, bSub) + a[a.Length - 1];                         else             {                 string x = lcsBack(a, bSub);                 string y = lcsBack(aSub, b);                 return (x.Length > y.Length) ? x : y;             }                     }     } }

Hey, danke dir für deine Mühe!

Stimmt, die Lösung wurde mir jetzt klar... nur verstehe ich nicht wieso er so merkwürdig hochgezählt hat. Ich meine, wieso sind die rot-markierten Kästchen rot-markiert? Wieso ausgerechnet diese? Wenn man z.B. links in der ersten Spalte das erste C (der y-Achse) mit dem C (der x-Achse) findet, dann wird von 0 auf 1 gezählt. Aber genau in der nächsten Zeile (eins drunter) ist auch wieder ein C, aber da bleibt der Counter immernoch auf 1. Und dort wird dann rot markiert... versteh den Sinn dahinter nicht so wirklich? Also, warum rot markiert wird und warum der Counter dort nicht erhöht wird...