Best Practice Palindrom in einem Text finden

[rspi]

Hallo liebe Gemeinde,
ich bin neu hier und scheitere daran eine Programm zu schreiben welches aus einem Text mir alle Palindrome die Wort übergreifend vorkommen übergibt..
Ein Programm das ein Palindrom erkennt habe ich schon, nur kann das halt den String im gesamten überprüfen.
Ich habe mir mal überlegt dass man eine Methode schreiben könnte, die die alle mögliche stellen die aneinader hängen teste. Gibt es da einen Algorithmus?

 

[stg]

Hallo liebe Gemeinde,
ich (...) scheitere daran eine Programm zu schreiben welches (...)

Dann zeig uns doch deine Ansätze und dann können wir hier gemeinsam schauen, woran es scheitert.

 

[strußi]

dein text ist ein string, mache daraus für jedes Wort ein String, schmeiß die Satzzeichen raus und dann schau ob es ein Palindrom ist

 

[Jardcore]

Lese den Text einfach Wort für Wort ein und prüfe mit deiner schon vorhandenen Methode.
Man kann auch eine Zeile einer Datei einlesen und dann diese Zeile mithilfe der split() Methode bei jedem Leerzeichen prüfen. Durch split() erhältst du ein Array von Strings, diese kannst du dann durchiterieren und wieder mithilfe deiner Methode analysieren.
Im Ansatz etwa so:

String[] words = line.split(" ");
for(String word : words) {
    checkPalindrom(word);
}

 

[VfL_Freak]

aus einem Text mir alle Palindrome die Wort übergreifend vorkommen

nur dass es eben wohl nicht nur für einzelne Wörter geprüft werden ... dies ist wohl der entscheidende Passus !!
Habe ich allerdings so aus dem Stand auch keine sinnvolle Idee
Gruß Klaus

EDIT: evtl. immer zwei aufeinanderfolgende Wörter konkatenieren und dann prüfen ...

 

[Elenteria]

wie wärs denn mit sowas

for(int substringLength = 1; substringLength < string.length; substringLengh++) {
  for(substringStart = 1; substringStart + substringLength < string.length; substringStart++) {
    String substring = string.subspring(substringStart, substringStart + substringLength);
    removeWhitespaces(substring);
    removePunctationsMarks(substring);
    checkPalindom(substring)
  }
}

Alle möglichen Substrings duchgehen, leerzeichen entfernen, Satzzeichen entfernen und prüfen ob der Substring ein Palindrom ist.

 

[stg]

Man muss bei Weitem nicht alle SubStrings durchgehen. Da explodiert schon bei relativ kurzen Texten die Laufzeit. Man muss schon ein bisschen "klug" dabei vorgehen, um wenigstens die mittlere Laufzeit klein zu halten.
Lösungen gibt es verschiedene und die meisten sind auch kein Hexenwerk. In meiner ersten Antwort hab ich aber bewusst keinen Lösungsansatz gepostet .. wir wollen hier doch keine Hausaufgaben für andere lösen, ohne dass auch nur ansatzweise der Versuch gezeigt wird, dass sich mit dem Problem beschäftigt wurde.

 

[Jardcore]

Heißt Wort übergreifend sowas: "..nebenAN NAchts am Strand..." ?

 

[VfL_Freak]

so verstehe ich den Eingangspost !!

 

[Jardcore]

Da kommt mir gleich die Frage, wann ist Schluss mit der Suche. Also wann ist die Abbruchbedingung gegeben. Ich könnte bei jedem Text davon ausgehen, dass er ab einer bestimmten Stelle nochmal in gespiegelter Form vorliegt. Also immer erwarten, dass irgendwann schon ein Palindrom kommt.

Wenn ich jetzt "abcdefghijklmnopqrstuvwxyzäüöß123456789" durchgehe kann es ja sein das am Ende dann "987654321ßöüäzyxwvutsrqponmlkjihgfedcba" kommt... oder auch nicht^^

 

[JCODA]

Aufgabe 3 ist dein Problem.
https://www1.ethz.ch/cadmo/education/lectures/FS14/DA/Pruefungen/2013-08-Pruefung.pdf
Die Lösung findet man hier:
https://www1.ethz.ch/cadmo/education/lectures/FS14/DA/Pruefungen/2013-08-Loesung.pdf

Stichwort hierzu ist dynamische Programmierung. (Natürlich musst du bei deinem Anwendungsszenario noch Leerzeichen/Satzzeichen entfernen und auf Groß/Kleinschreibung achten, aber das ist ja ziemlich einfach.)

 

[Xyz1]

Wie wär's damit:

package javaapplication;

/**
 *
 */
public class Temp {

    public static void main(String[] args) {
        String s = "Halla, mal ein Testproggo, bararabbelol";
        int idx = 1;
        for (int i = 0; i < s.length(); i++) {
            for (int j = s.length(); i + 1 /* mindestlaenge 2 */ < j; j--) {
                if (isPali(s, i, j)) {
                    System.out.println(idx++ + ": " + s.substring(i, j));
                    i = j;
                }
            }
        }
    }

    private static boolean isPali(String string, int from, int to) {
        to--;
        while (from < to) {
            if (string.charAt(from) != string.charAt(to)) {
                return false;
            }
            from++;
            to--;
        }
        return true;
    }
}

run:
1: alla
2: oggo
3: bararab
4: lol
BUILD SUCCESSFUL (total time: 0 seconds)

Ich habe jetzt mehrere Minuten für diese Aufgabe gebraucht, und auch noch nicht die Tests geschrieben. Also für eine Prüfung würd ich das nicht empfehlen.

 

[JStein52]

Ist aber noch nicht ganz komplett oder ? Müsste er nicht auch "ll", "gg", "ara", "arara", "bb" finden ?

 

[Cromewell]

Dann aber auch "rar"

 

[Xyz1]

Keine Wörter in Wörtern... Wenn doch (das hatte ich zunächst):

package javaapplication;

/**
 *
 */
public class Temp {

    public static void main(String[] args) {
        String s = "Halla, mal ein Testproggo, bararabbelol";
        int idx = 1;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 2; j <= s.length(); j++) {
                if (isPali(s, i, j)) {
                    System.out.println(idx++ + ": " + s.substring(i, j));
                }
            }
        }
    }

    private static boolean isPali(String string, int from, int to) {
        to--;
        while (from < to) {
            if (string.charAt(from) != string.charAt(to)) {
                return false;
            }
            from++;
            to--;
        }
        return true;
    }
}

run:
1: alla
2: ll
3: oggo
4: gg
5: bararab
6: ara
7: arara
8: rar
9: ara
10: bb
11: lol
BUILD SUCCESSFUL (total time: 0 seconds)

Das ist aber wirklich "unschön", man soll ja auch etwas mit den Ergebnissen anfangen sollen.

 

[JStein52]

Das ist aber wirklich "unschön", man soll ja auch etwas mit den Ergebnissen anfangen sollen

Was ist an so einer Aufgabenstellung unschön ?

 

[Xyz1]

Was ist an so einer Aufgabenstellung unschön ?

String processing finde ich jetzt nicht so spannend, es sei denn, es sind DNA, dann finde ich es selbstverständlich spannend.

Leider habe ich hier kein Gerät zum Erkennen von DNA. Ist sowas teuer?

 

[JStein52]

Leider habe ich hier kein Gerät zum Erkennen von DNA. Ist sowas teuer

Nö, gibts bestimmt bei Amazon.

String processing finde ich jetzt nicht so spannend

Aber um ein bisschen Java-Fingerfertigkeit zu kriegen ist es doch ok ?

 

[Xyz1]

OT:

Nö, gibts bestimmt bei Amazon.

Wenn man mal nach "dna extraction machine price" sucht, sieht man, die Hersteller geben den Preis einfach nicht an! Als Privatperson hat man immer nu Probs.^^[/OT]

Aber um ein bisschen Java-Fingerfertigkeit zu kriegen ist es doch ok ?

Stimmt schon, ich kritisiere ja nicht die Aufgabenstellung, sondern deren/die Lösung. (Also meine )