Anstatt 1 int Rückgabewert, mehrere Rückgaben mit Arraylist

[Mofdesa]

Hallo zusammen,

Ich habe 1 Klasse in der ich den KMP-Search Algorithmus implementiert habe. Dieser liefert die erste Fundstelle für ein Pattern als int zurück. Funktioniert auch soweit. Nun hätte ich allerdings gerne ALLE Fundstellen des Patterns zurückgegeben. Wollte hierfür die ArrayList benutzen. Nun funktioniert es manchmal. Wenn das Pattern allerdings vor der Stelle 3 gefunden wird, oder mehrmals vorkommt, funktioniert es nicht.

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 1
	at java.lang.String.charAt(String.java:694)
	at Suchalgorithmen.kmpSearch(Suchalgorithmen.java:25)
	at Testprogramm.main(Testprogramm.java:33)

Ich verstehe nicht warum der Index mal passt und mal nicht. Kann mir jemand auf die Sprünge helfen? Vielen Dank!

public class Testprogramm{
	public static void main(String[] args) {
	System.out.print(Suchalgorithmen.kmpSearch("baaab", "b"));
}
}

public class Suchalgorithmen {
public static int kmpSearch (String text, String pat) {
		int[] next = initNext (pat);
		int i = 0, j = 0;
		while (i < text.length()) {
			while (j >= 0 && pat.charAt(j) != text.charAt(i))
			j = next[j];
			i++; j++;
			if (j == pat.length()) return i - pat.length();  //gefunden
			}
		
		return -1;//-1; // nicht gefunden
		}
	
	private static int[] initNext (String pattern) {
		int[] next = new int [pattern.length ()];
		int i = 0, j = -1;
		next[0] = -1;
		while (i < pattern.length() - 1) {
		while (j >= 0 && pattern.charAt(i) !=
		pattern.charAt(j))
		j = next[j];
		i++; j++;
		next[i] = j;
		}
		return next;
		}
}

Implementierung mit ArrayList

public static ArrayList<Integer >kmpSearch (String text, String pat) {
		ArrayList<Integer> gefundene_positionen_kmp = new ArrayList<Integer>();
		int[] next = initNext (pat);
		int i = 0, j = 0;
		while (i < text.length()) {
			while (j >= 0 && pat.charAt(j) != text.charAt(i))
			j = next[j];
			i++; j++;
			if (j == pat.length()) gefundene_positionen_kmp.add(i - pat.length());
			}
		if (gefundene_positionen_kmp.isEmpty()) return null;
		else return gefundene_positionen_kmp;
		}

 

[njans]

       while (i < pattern.length() - 1) {
        while (j >= 0 && pattern.charAt(i) !=
        pattern.charAt(j))
        j = next[j];
        i++; j++;
        next[i] = j;

Was sollte j daran hindern über pattern.length -1 hin wegzugehen und dir dann deine Exception zu werfen?

Nebenbei: Bitte schreibe doch Java und nicht C, Java hat nämlich so seine Code Conventionen, welche sich auch leicht lesen lassen.

 

[Mofdesa]

Vielen Dank für deine Antwort. Ich verstehe deine Frage nicht wirklich. j wird doch nur mit 0 und pattern.charAt(i) verglichen.

Ich hatte mir das einfach so gedacht, dass anstelle der Rückgabe des int Wertes, dieser in die Liste geschrieben wird. Sonst will ich ja an der Arbeitsweise nichts ändern.

Was meinst du mit C und Java? Hab doch den Code in Java Tags gesetzt.

 

[imillitay]

Dadurch, dass du jetzt nach dem Fund einer Stelle weitermachst und das Programm nicht abbrichst, wird j weiter erhöht. Und was wird passieren, wenn j zuletzt genauso groß war wie die Länge des gesuchten Strings und dann noch um eins erhöht wird?

Bezüglich C und Java: njans meint vermutlich Variablennamen wie

gefundene_positionen_kmp

(Stichwort CamelCase)

Korrekte Einrückungen können den Code auch um einiges lesbarer machen.

 

[Mofdesa]

Pling. Der Groschen ist gefallen. Dann ist String nicht mehr in der Range und ich bekomme selbstverständlich meine Exception an der Stelle:

while (j >= 0 && pat.charAt(j) != text.charAt(i))

Richtig? Nun weiß ich schonmal wo das Problem liegt. Das ist sehr hilfreich, vielen Dank. Wenn ich jetzt j nur erhöhe, wenn die if-Bedingung nicht zutrifft, wäre das der richtige Weg?

Das mit den Variablennamen und den Einrückungen bitte ich an der Stelle zu entschuldigen. Bin nicht so fit in den Java Conventions.

 

[imillitay]

Dann hättest du immer noch das Problem, dass dein j irgendwann ins Unendliche schießt.
Denk daran, dass du, nachdem du ein Wort gefunden hast, an der nächsten Stelle im zu durchsuchenden String weitermachst und der Algorithmus beim Pattern wieder von vorne beginnen muss.

 

[Mofdesa]

Nochmals vielen Dank. Das habe ich heute auch gemerkt. ;-) Hätte nicht gedacht, dass das so schwierig wird.

Auf jeden Fall kriege ich das auf die Schnelle nicht gelöst und mir fehlt gerade die Zeit, um mich damit ausführlich zu beschäftigen. Werde da wohl Ende der Woche nochmal in Ruhe dran gehen. Kenne mich in Java noch nicht so gut aus, aber sowas wie Sprungpunkte gibt es ja auch sicherlich.

 

[imillitay]

So schwierig ist das denke ich nicht, bei mir hat eine weitere Anweisung gereicht und es lief (welche und wo verrate ich dir aber nicht )
Zumindest hat es drei kleine Tests von mir ueberstanden. Hier bietet sich uebrigens JUnit perfekt an, um mehrere Tests fuer deinen Algorithmus zu schreiben.

 

[Mofdesa]

Ist wahrscheinlich wie immer, wenn man es gelöst hat, war es eigentlich ganz einfach. ;-)

Will da schon selber drauf kommen, da bin ich ehrgeizig... Da ich ja jetzt grundsätzlich weiß, wo der Fehler liegt, bekomme ich das sicherlich auch hin. Aber jetzt fehlt mir gesagt die Zeit und ich bin "codeblind", wenn du verstehst was ich meine. ;-) War wohl ein wenig optimistisch zu denken, dass ich mich mal schnell in Java zurecht finde. :-D