Boyer
Boyer-
-Moore
Moore
Ví dụ:
P= m=5, j=m-1=4
T= n=12,s=0
1. T[4+0] # P[4] j=4,k=last(T[4],P)=3,s=0+1=1
2. s=1,j=4,T[4+1] = P[4] j=4-1=3
3. T[3+1] = P[3] j=3-1=2
4. T[2+1] # P[2] j=2,k=last(T[3],P)=4,s=1+1=2
5. s=2,j=4,T[4+2] # P[4] j=4,k=last(T[6],P)=2, s=2+2=4
6. s=4,j=4,T[4+4] = P[4] j=4-1=3
0 1 2 3 4
A B C A B
0 1 2 3 4 5 6 7 8 9 10 11
A C B B A B C A B A B C
Boyer
Boyer-
-Moore
Moore
Ví dụ:
P= m=5, j=m-1=4
T= n=12,s=0
7. s=4,j=3,T[3+4] = P[3] j=3-1=2
8. s=4,j=2,T[2+4] = P[2] j=2-1=1
9. s=4,j=1,T[1+4] = P[1] j=1-1=0
10. s=4,j=0,T[0+4] = P[0] j=0-1=-1
Tìm thấy P trong T tại s=4
0 1 2 3 4
A B C A B
0 1 2 3 4 5 6 7 8 9 10 11
A C B B A B C A B A B C
Boyer
Boyer-
-Moore
Moore
Đánh giá thuật toán:
- Hàm Last: O(m+n)
- Boyer-Moore: Tình huống xấu nhất O(mn+n)
- VD: P=bam-1; T=an
Boyer
Boyer-
-Moore
Moore
Bài tập:
1. Tìm Prefix của mẫu sau:
a. ABABBC
b. BBABBA