Scriba — kmp

Step 1 / 24

KMP tim mau $P$ = ABABCABAB trong chuoi $T$ = ABABDABACDABABCABAB. Hai pha: (1) dung bang that bai $F[i]$ tren $P$ , (2) duyet $T$ mot lan, dung $F$ de nhay lui $j$ khi khong khop – khong bao gio lui $i$ .

Step 2 / 24

Pha 1 – xay $F$ . Quy uoc $F[0] = 0$ : khong co tien to that su nao co the la hau to cua chinh ky tu dau.

Step 3 / 24

$i=1$ : so sanh $P[1]=$ B voi $P[0]=$ A. Khac nhau, khong co tien to nao trung – $F[1]=0$ .

Step 4 / 24

$i=2$ : $P[2]=$ A = $P[0]=$ A. Do dai tien to trung dai nhat tang tu 0 len 1 – $F[2]=1$ .

Step 5 / 24

$i=3$ : mo rong tien to dai 1 – so sanh $P[3]=$ B voi $P[F[2]]=P[1]=$ B. Khop, do dai len 2 – $F[3]=2$ .

Step 6 / 24

$i=4$ : $P[4]=$ C vs $P[F[3]]=P[2]=$ A. Khong khop – lui $j \leftarrow F[1]=0$ , thu lai $P[4]$ vs $P[0]=$ A: van lech. $j$ da ve 0, dung – $F[4]=0$ .

Step 7 / 24

$i=5$ : $P[5]=$ A = $P[0]=$ A. $F[5]=1$ .

Step 8 / 24

$i=6$ : $P[6]=$ B = $P[1]=$ B. $F[6]=2$ .

Step 9 / 24

$i=7$ : $P[7]=$ A = $P[2]=$ A. $F[7]=3$ .

Step 10 / 24

$i=8$ : $P[8]=$ B = $P[3]=$ B. $F[8]=4$ . Bang that bai hoan tat: $F = [0,0,1,2,0,1,2,3,4]$ .

Step 11 / 24

Pha 2 – quet $T$ . Con tro $i$ chay tren $T$ , $j$ chay tren $P$ . Khi khop: ca hai tien. Khi lech: $j \leftarrow F[j-1]$ (khong bao gio lui $i$ ).

Step 12 / 24

$i=0, j=0$ : $T[0]=$ A = $P[0]=$ A. Ca hai tien.

Step 13 / 24

Bon vong khop lien tiep ABAB. Bay gio $i=3, j=3$ va $T[3]=$ B = $P[3]=$ B – chuan bi kiem $T[4]$ .

Step 14 / 24

$i=4, j=4$ : $T[4]=$ D vs $P[4]=$ C. Lech! Tra $F[j-1] = F[3] = 2$ : con tro $j$ nhay lui ve vi tri $2$ , giu $i=4$ .

Step 15 / 24

$j=2$ : thu lai $T[4]=$ D vs $P[2]=$ A. Van lech – tra $F[1] = 0$ : $j$ nhay ve $0$ .

Step 16 / 24

$j=0$ : $T[4]=$ D vs $P[0]=$ A. Lech, $j$ da $0$ – tien $i$ , giu $j=0$ .

Step 17 / 24

$i=5, j=0$ : $T[5]=$ A = $P[0]=$ A. Bat dau khop lai.

Step 18 / 24

Khop them ABA. Bay gio $i=8, j=3$ : $T[8]=$ C vs $P[3]=$ B. Lech! Tra $F[j-1] = F[2] = 1$ : $j$ nhay lui ve $1$ .

Step 19 / 24

$j=1$ : $T[8]=$ C vs $P[1]=$ B. Lech – tra $F[0] = 0$ : $j$ nhay ve $0$ .

Step 20 / 24

$j=0$ : $T[8]=$ C vs $P[0]=$ A. Lech, $j$ da ve $0$ – tien $i$ , giu $j=0$ .

Step 21 / 24

$i=9$ : D vs A, lech, tien $i$ . $i=10, j=0$ : $T[10]=$ A = $P[0]$ . Bat dau lai. Lan nay se la phat an: tu $i=10$ toan bo 9 ky tu $T[10..18]$ se khop voi $P[0..8]$ .

Step 22 / 24

$i=10..14$ , $j=0..4$ : khop lien tiep ABABC. Bay gio $i=14, j=4$ : $T[14]=$ C = $P[4]=$ C. Tiep tuc khop – lan nay vuot qua vi tri truoc do bi lech.

Step 23 / 24

Khop tiep ABAB. $j$ dat $9 = |P|$ – tim thay mau hoan chinh! Vi tri bat dau: $i - |P| + 1 = 18 - 9 + 1 = 10$ .

Step 24 / 24

Khop toan bo $P$ voi $T[10..18]$ . KMP tim thay mau tai vi tri 10, tong cong $O(|T| + |P|)$ phep so sanh – con tro $i$ khong bao gio lui lai.