✔ KMP String-Suche

[fastfiler]

Hi,

ich weiss zwar nicht ob es das richtige forum ist, aber da ich es in java benötige denke ich es ist nicht ganz falsch plaziert.

es geht um den schönen KMP (Knuth-Morris-Pratt) algorithmus zum durchsuchen von strings nach zeichenketten. wie jeder weiss ist dieser ziemlich schnell - auch mit grösseren dateien bzw. strings. ich hab ihn mir mal angeschaut und möchte ihn dahingehgend modizfieren, dass er nicht nach der genauen zeichenfolge sucht

(suchstring.charAt(i) = string.charAt(j)

sondern immer einen buchstaben auslässt. ---> suchstring.charAt(i) = string.charAt(j+1)
schaut jetzt auf den ersten blick relativ einfach aus - aber diesen algorithmus schnell mal hinzubiegen - auch wenn man ihn schon vor sich hat - ist garnich so einfach.

hier mal ein konkretes beispiel wie er funktionieren soll.

zu durchsuchende zeichenkette:

bereitskurzeeitnachdemmitdemdasbstractindowing
oolkiteingefuhhatluldobegannendientwicklerbeiueber

suchstring: hallo

gefunden werden soll nun:

bereitskurzeeitnachdemmitdemdasbstractindowing
oolkiteingefuhhatluldobegannendientwicklerbeiueber

hier mal ein beispiel aus dem inet wie man ihn implementieren könnte

private boolean searchInFile (String sDatei, String sSuchString) {
		String sDateiStr=new String(sDatei); // String der durchsucht wird
		String sSuchStr=new String(sSuchString);
		int d[];
		int i=0,j=0,k=0;
		  
		d=new int[sSuchStr.length()]; // Fuer jedes Zeichen ein Eintrag
		d[0]=-1;
		  
		while (j<sSuchStr.length()-1) {
		  while ((k>=0) && (sSuchStr.charAt(j)!=sSuchStr.charAt(k))) {
		    k=d[k];
		  }
		  j++;
		  k++;
		  if (sSuchStr.charAt(j)==sSuchStr.charAt(k)) {
		    d[j]=d[k];
		  } else {
		    d[j]=k;
		  }
		}
		i=0;
		j=0;
		k=0;
		while ((j<sSuchStr.length()) && (i<sDateiStr.length())) {
		  while (k<=i) {
		    k++;
		  }
		  while ((j>=0) && (sDateiStr.charAt(i+1)!=sSuchStr.charAt(j))) {
		    j=d[j];
		  }
		  i++;
		  j++;
		}
		if (j==sSuchStr.length()) { // Suchstring gefunden
		  return true;  
		} else {
		  return false;
		}
	}

hat vielleicht schon mal jmd so etwas ähnliches gemacht?

mfg & thx

fasti