ACM ICPC Praktikum

ACM ICPC Praktikum

Kapitel 3: Strings

Übersicht

• Notation

• Naives String-Matching

• Knuth-Morris-Pratt Algorithmus

• Aho-Corasick Algorithmus

• Matching regulärer Ausdrücke

Grundlegende Definitionen

• Alphabet Endliche Menge von Symbolen

• Wort (String, Zeichenkette) w über endliche Folge von Symbolen aus

• n: Menge aller Wörter der Länge n

• * = n >=0 n, + = n > 0 n

• x ± y: Konkatenation von Worten x und y

Grunglegende Definitionen

• s ist ein Teilwort von t, falls es ein i gibt mit s=(ti,…,ti+|s|-1)

• s heißt Präfix von t, falls i=1

• s heißt Suffix von t, falls i=|t|-|s|+1

t

s s

t= =

Präfix Suffix

Exaktes Stringmatching

• Variante 1: Gegeben zwei Wörter s und t, finde erstes Vorkommen von s in t

• Variante 2: Gegeben zwei Wörter s und t, finde alle Vorkommen von s in t

• Hier: überwiegend Variante 2

Naiver Algorithmus

m=|s|;n=|t|;for i=1 to n-m+1 do j=1; while (j<=m and

s[j] = t[i+j-1]) do j=j+1; if (j>m) then “gib i aus”

…….

t

s

KMP-Algorithmus

• Idee: Falls für ein i und j gilt (s1...sj)=(ti…ti+j-1) und sj+1<>ti+j

dann erhöhe i zum nächsten i’ mit (s1…sj-(i’-i)) = (ti’…ti+j-1) und vergleiche weiter bei j’=j-(i’-i)+1.

t

s= =

s=

KMP-Algorithmus

• Preprocessing:Bestimme für jedes i minimales d(i)>1, so dass (s1...si-d(i)+1) = (sd(i)...si).

• Algorithmus:d[0]=2; d[1]=2; j=2;for i=2 to m do while (j<=i and s[i]<>s[i-j+1]) j=j+d[i-j]-1; d[i]=j;

KMP-Algorithmus

• Knuth-Morris-Pratt Algorithmus:

führe KMP-Preprocessing durchi=1; // aktuelle Position in t j=1; // aktuelle Anfangsposition von s in twhile (i<=n) do if (j<=i and t[i]<>s[i-j+1]) then j=j+d[i-j]-1; else if (i-j+1=m) then “gib j aus”; j=j+d[m]-1; i=i+1;

Aho-Corasick Algorithmus

• Problem: suche in t nach allen Vorkommen von Wörtern in Menge S

• Idee: verwende endlichen Automaten

• Beispiel: abaaba

0 1 2 3 4 5 6a

a

a a

a

ab

b

b

bb

b

a


• Beispiel: abaaba

• AC-Automat mit Fehlerübergängen

0 1 2 3 4 5 6a a a ab b


• Preprocessing:Bestimme für jedes i minimales d(i)>1, so dass (s1...si-d(i)+1) = (sd(i)...si). Setze f(i)=i-di+1.

• Algorithmus:d[0]=2; d[1]=2; j=2;for i=2 to m do while (j<=i && s[i]<>s[i-j+1]) j=j+d[i-j]-1; d[i]=j;for i=0 to m do f[i]:=i-d[i]+1;


• AC Algorithmus:

führe AC-Preprocessing durchj=0; // aktuelle Postion im Automatenfor i=1 to n do while (j<>-1 and t[i]<>s[j+1]) do j=f[j]; // Fehler: starte neuen Versuch if (j=-1) then j=0; else j=j+1; if (j=m) then “gib j aus”;


• Suchwortmenge S={ab,ba,babb,bb}: Trie

0

4

1

6

2

3 5

7

b

a

a

b

b

b

b


• Zustandsmenge:Q = {w2 * j w Präfix von s 2 S}q0 =

• Endzustände: F = F1 [ F2 mit- F1 = S- F2 = {w 2 Q j 9 s 2 S: s echtes Suffix von w}

• Übergänge:- (w,a) = wa für alle w,wa 2 Q- (w,fail) = w’ für das w’ 2 Q, das den längesten echten Suffix von w darstellt


• Suchwortmenge S={ab,ba,babb,bb}:

0

4

1

6

2

3 5

7

b

a

a

b

b

b

b


• AC-Preprocessing (Teil 1): (mk = |sk|, m = k |mk|)

// d[q][c]: für Übergang von q bei Zeichen c// d[q][0] 2 {1,…,|S|}: gibt Suchwort an, wenn q 2 F// s[k][i]: i-tes Zeichen in skfor q=0 to m do // initialisiere d for c=0 to || do d[q][c]=0qnew = 1; q = 0;for k=1 to |S| do // konstruiere Trie for i=1 to mk do if d[q][s[k][i]]=0 then d[q][s[k][i]] = qnew; qnew = qnew+1; q = d[q][s[k][i]]; d[q][0] = k // setze Endzustand für sk

Aho-Corasick Algorithmus• AC-Preprocessing (Teil 2):

// f[q]: Fehlerfunktion für Zustand qf[0] = -1; Q = new Queue;for c=1 to || do if d[0][c]<>0 then f[d[0][c]] = 0; // Fehlerfunktion aller Söhne von Start auf Start enqueue(Q,f[d[0][c]]);while not empty(Q) do // BFS über alle Zustände q q = dequeue(Q); for c=1 to || do if d[q][c]<>0 then // Nachfolgezustand definiert? q’ = d[q][c]; r = f[q]; while (r<>0 and d[r][c]=0) do r=f[r]; // berechne Fehlerfunktion f[q’] = d[r][c]; if (d[f[q’]][0]>0 and d[q’][0]=0) then // q’ in F2? d[q’][0] = d[f[q’][0]]; enqueue(Q,q’);


• Allgemeiner AC-Algorithmus:

führe AC-Preprocessing durchq = 0; // aktuelle Position des Automatenfor i=1 to n do while (q<>-1 and d[q][t[i]]=0) do q = f[q]; if (q=-1) then q=0; else q=d[q][t[i]]; if d[q][0]>0 then gib i-md[q][0]+1 und d[q][0] aus

Matching regulärer Ausdrücke

• Problem: geben Text t und regulärer Ausdruck r, gib aus, ob r in t vorkommt

• Idee: konstruiere aus r endlichen Automaten

• Konstruktion basiert auf 5 Regeln

Konstruktion eines NEA

• Für die elementaren regulären Ausdrücke ;, , und c 2 werden die folgenden drei Automaten konstruiert:

c


• Gegeben r1 und r2 und deren NEAs N1 und N2, der NEA für r1+r2 ist:

N1

N2

neuer Anfangs-zustand

neuer End-zustand


• Gegeben r1 und r2 und deren NEAs N1 und N2, der NEA für r1¢ r2 ist:

N1 N2


neuer End-zustand


• Gegeben r1 dessen NEA N1, der NEA für r1* ist:

N1


neuer End-zustand


Bemerkungen:• Der so konstruierte NEA für einen Ausdruck r mit m=|r|

hat höchstens 2m Zustände.• Die Regeln benötigen jeweils nur konstante Zeit.• Der NEA für r hat genau einen Start- und Endzustand.• Der Startzustand hat keine eingehende Kante und der

Endzustand keine ausgehende Kante.• Jeder Zustand hat entweder

- genau eine ausgehende Kante für jedes c 2 - oder höchstens zwei mit \epsilon markierte ausgehende Kanten


Satz: Zu jedem regulären Ausdruck r kann in O(m) Zeit ein äquivalenter NEA mit -Übergängen konstruiert werden.

Beispiel: NEA zu (a+b)*aba

a

a ab

b

Simulation eines NEA

Bemerkungen:• Im folgenden Algorithmus bezeichnet qstart den

Startzustand und qend den Endzustand.• Q is eine Menge von Zuständen.• (Q,c) bezeichnet die Menge aller Zustände, die

von einem Zustand aus Q über eine mit c markierte Kante erreichbar sind.

• Da das Muster an einer beliebigen Stelle des Textes auftreten kann, wird in jeder Iteration der Startzustand qstart zur aktuellen Zustandsmenge hinzugenommen.

Simulation des NEA

• Algorithmus:

Q = eps({qstart});if qend 2 Q then return truefor i=1 to n do Q = eps((Q,t[i]) [ {qstart}) if qend 2 Q then return truereturn false

• Laufzeit: O(n ¢ m) im worst case.

Documents

ACM ICPC Praktikum