Kürzeste Wege SS12

Aus ProgrammingWiki

Archivierte Version vom 2014-01-20T03:26:58+00:00. Aktuelle Version

Aufgabe 1

void bmh(String text, String wort){
		  int laengeText = text.length();
		  int laengeWort = wort.length();		  
		  int position = 0;
		  int aktZeichen;
		  int zaehlerStellen=0;
		  boolean gefunden = false;
		  while (position <= laengeText-laengeWort){
		  aktZeichen = 0;
		  zaehlerStellen++;
		  while (aktZeichen < laengeWort && wort.charAt(aktZeichen)==text.charAt(position+aktZeichen)){
		      aktZeichen++;
		    }
		    if (aktZeichen == laengeWort){
		      System.out.println("Wort an der Stelle " + (position+1) + " im Text gefunden.");
		      gefunden=true;
		    }
		    position++;
		  }
		  if (gefunden == false)
		    System.out.println("Keine Treffer bei der Suche.");
		  System.out.println(zaehlerStellen + " Stellen wurden durchsucht.");
		}

Aufgabe 2

void bmh(String t, String w){
	int n = t.length();
	int m = w.length();
	int[] d = badCharacter(w,m);
	int pos = 0;
	int j;
	int zS=0;
	boolean g = false;
	while (pos <= n-m+1){
		zS++;
		j = m;
		while (j > 0 && w.charAt(j-1) == t.charAt(pos+j-2))
			j--;
		if (j == 0){
			System.out.println("Wort an der Stelle " + (pos) + " im Text gefunden.");
			g = true;
		}
		pos += d[(int)t.charAt(pos+m-2)];
	}
	if (g == false)
		System.out.println("Keine Treffer bei der Suche.");
	System.out.println(zS + " Stellen wurden durchsucht.");
}

int[] badCharacter(String w, int m){
	int[] d = new int[256];
	for (int i = 0;i<256;i++)
		d[i] = m;
	char c;
	for (int i = 0;i<m-1;i++){
		c = w.charAt(i);
		d[(int)c] = (i-m)*-1-1;
	}
	return d;
}

Aufgabe 3

Übergangsfunktion in Form einer Tabelle:

\delta	a	b	c
0	0	0	1
1	0	2	1
2	0	0	3
3	0	2	4
4	0	5	1
5	6	0	3
6	0	0	7
7	0	8	1
8	0	0	3

Analyse: ein DEA akzeptiert nur vollständig gelesene Wörter und nur dann, wenn der Zustand nach dem vollständigen Lesen ein Endzustand ist. Somit ist er nicht in der Lage mehrere Vorkommen eines Wortes in einem Text zu finden bzw. nur wenn das Wort an der Stelle n-m+1 im Text steht. Änderung: DEA in NEA umwandeln und die Übergänge für alle \Sigma von q_m nach q_m ergänzen.

Aufgabe 4

i	1	2	3	4	5	6	7	8	9	10
w[i]	b	c	b	c	c	b	c	b	c	a
\pi[i]	0	0	1	1	2	3	2	3	0	0