AuK/Kürzeste Wege SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
'''Aufgabe 1'''
<code>
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.");
}
</code>
'''Aufgabe 2'''
<code>
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;
}
</code>
'''Aufgabe 3'''
Übergangsfunktion in Form einer Tabelle:
{| class="wikitable"
!$\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'''
<table border="1">
<tr>
<td style="text-align:center;width: 5mm;" bgcolor="#D8D8D8">$i$</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''4'''</td>
<td style="text-align: center;width: 5mm;">'''5'''</td>
<td style="text-align: center;width: 5mm;">'''6'''</td>
<td style="text-align: center;width: 5mm;">'''7'''</td>
<td style="text-align: center;width: 5mm;">'''8'''</td>
<td style="text-align: center;width: 5mm;">'''9'''</td>
<td style="text-align: center;width: 5mm;">'''10'''</td>
</tr>
<tr>
<td style="text-align:center;width: 5mm;" bgcolor="#D8D8D8">$w[i]$</td>
<td style="text-align: center;width: 5mm;">'''b'''</td>
<td style="text-align: center;width: 5mm;">'''c'''</td>
<td style="text-align: center;width: 5mm;">'''b'''</td>
<td style="text-align: center;width: 5mm;">'''c'''</td>
<td style="text-align: center;width: 5mm;">'''c'''</td>
<td style="text-align: center;width: 5mm;">'''b'''</td>
<td style="text-align: center;width: 5mm;">'''c'''</td>
<td style="text-align: center;width: 5mm;">'''b'''</td>
<td style="text-align: center;width: 5mm;">'''c'''</td>
<td style="text-align: center;width: 5mm;">'''a'''</td>
</tr>
<tr>
<td style="text-align:center;width: 5mm;" bgcolor="#D8D8D8">$\pi[i]$</td>
<td style="text-align: center;width: 5mm;">'''0'''</td>
<td style="text-align: center;width: 5mm;">'''0'''</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''0'''</td>
<td style="text-align: center;width: 5mm;">'''0'''</td>
</tr>
</table>