wie soll man in diese Aufgabe vorgehen java / Mathe String?

Hallo, könnt ihr mir bitte bei dieser Aufgabe helfen ?

Ich habe nicht viel programmier Erfahrung, wäre nett wenn ihr es so einfach wie es geht beschreibt.

Und wie ich es am besten lösen kann :D

Klausuraufgabe 1.Semester

Answer 1

[PerfectMuffin]

Bei welchem Teil brauchst du Hilfe?

Comments

[Rudinatooor]

ich verstehe leider die Aufgabenstellung nicht

[PerfectMuffin]

@Rudinatooor

Weißt du, wie man eine Methode schreibst?

Weißt du wa smit größtem gemeinsamen Substring gemeint ist?

[Rudinatooor]

@PerfectMuffin

ja ich weiß wie alles aufgebaut wird, (methode etc.)

aber das mit den gemeinsamen Substring verstehe ich nicht ganz

[PerfectMuffin]

@Rudinatooor

Ein Substring ist eine Zeichenkette in einem String.

z.b. "abc" hat die substrings "a","b","c","ab","bc" und "abc"

Answer 2

[tavkomann]

Die Aufgabenstellung sollte soweit verständlich sein: Es ist eine Methode gesucht, die aus zwei Zeichenketten die Länge der längsten gemeinsamen Teilzeichenkette berechnet. Schreiben wir das erst einmal hin:

int longEq(String s, String t) {

}

Nun benötigen wir irgendwie eine Variable, in der wir die Länge der zurzeit längsten ermittelten Zeichenkette abspeichern. Am Ende geben wir den Wert, der in dieser Variable gespeichert ist, zurück:

int longEq(String s, String t) {
  int maxLength = 0;
 
  // Magie ;-) 
  
  return maxLength;
}

Nun kümmern wir uns um die „Magie“. Die intuitivste Möglichkeit ist sicherlich, einfach alle möglichen Teilzeichenketten durchzugehen. Wie wird eine Teilzeichenkette charakterisiert? Es gibt eine Startposition und eine Länge bzw. eine Endposition, die sich aus Startposition und Länge ergibt.

Bauen wir uns also einfach eine Schleife, mit der wir jede einzelne Startposition in der einen Zeichenkette durchgehen:

int longEq(String s, String t) {
  int maxLength = 0;

  for (int i = 0; i < s.length(); ++i) {
    // ...
  }

  return maxLength;
}

Nun gehen wir innerhalb dieser Schleife mithilfe einer weiteren Schleife jede einzelne Länge durch. Wann brechen wir ab?

1. Das Ende der Zeichenkette ist erreicht
2. Die ermittelte Teilzeichenkette kommt in der anderen Zeichenkette gar nicht vor: Daher brauchen wir sie nicht noch weiter verlängern.

Im Code sieht das so aus:

int longEq(String s, String t) {
  int maxLength = 0;

  for (int i = 0; i < s.length(); ++i) {
    int l;
    for (l = 0; i+l < s.length()
        && t.contains(s.substring(i, i+l+1)); ++l);
  }

  return maxLength;
}

Nicht verwirren lassen: Eine Schleife muss keinen Schleifenkörper besitzen. Die Schleife dient hier nur zum Zählen und uns interessiert am Ende nur der Wert der Variable l. Deshalb lagern wir die Deklaration dieser Variable aus der Schleife aus, damit wir auch außerhalb der Schleife auf sie zugreifen können.

Nun fehlt uns nur noch ein Schritt: Wenn die ermittelte Länge größer als die bisherige Maximallänge ist, speichern wir sie ab. Der fertige Code sieht daher so aus:

int longEq(String s, String t) {
  int maxLength = 0;

  for (int i = 0; i < s.length(); ++i) {
    int l;
    for (l = 0; i+l < s.length()
        && t.contains(s.substring(i, i+l+1)); ++l);
    if (l > maxLength) maxLength = l;
  }

  return maxLength;
}

Hier ein Live-Beispiel: https://repl.it/@tavkomann/LongEq

Der Code ist bezüglich der Performance noch nicht optimal, aber eine Lösung der Aufgabe wird durch ihn auf jeden Fall erreicht.

Comments

[ralphdieter]

Performance noch nicht optimal

Eine ganz billige Beschleunigung:

  for (l=maxlength; i+l < s.length()

[tavkomann]

@ralphdieter

Genau. Ebenso könnte man schauen, dass man den kürzeren der beiden Strings durchläuft.

[Rudinatooor]

danke für die ausführliche Antwort, :D habe es nun verstanden

Answer 3

[hallo98863]

Du gehst nach und nach alle möglichen Substrings durch, nimmst halt immer einen Buchstaben weg und schaust, ob dieser Substring im 2. String ist

Comments

[Rudinatooor]

kannst du mir vielleicht ein Beispiel code schreiben ?

wäre echt super