Cấu trúc dữ liệu và giải thuật (phần 13)

Trong phần này các bạn sẽ được làm rõ từng bước của thuật toán KMP thực hiện như thế nào, tại sao nó thông minh và hiệu qủa đến vậy, hãy ngâm cứuứu
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật (phần 13) Knuth-Morris-Pratt Knuth Ví d :T=”abcabcabcaababcba” P=”abcabca”P=”abcabca” PI[1]=0P=”abcabca” PI[2]=0P=”abcabca” PI[3]=0P=”abcabca” PI[4]=1P=”abcabca” PI[5]=2P=”abcabca” PI[6]=3P=”abcabca” PI[7]=4 Knuth-Morris-Pratt Knuthq=0; T=”abcabcabcaababcba” P=”abcabca”• i=1: P[0+1]=T[1] q++ q=1• i=2: P[1+1]=T[2] q++ q=2• i=3: P[2+1]=T[3] q++ q=3• i=4: P[3+1]=T[4] q++ q=4• i=5: P[4+1]=T[5] q++ q=5• i=6: P[5+1]=T[6] q++ q=6• i=7: P[6+1]=T[7] q++ q=7 Xu t s=1 Knuth-Morris-Pratt Knuthq=PI[7]= 4 P=”abcabca” T=”abcabcabcaababcba• i=8: P[4+1]=T[8] q++ q=5• i=9: P[5+1]=T[9] q++ q=6• i=10:P[6+1]=T[10] q++ q=7 Xu t s=4q=PI[7]= 4 P=”abcabca” T=”abcabcabcaababcba• i=11: P[4+1]T[11] q=PI[4]=1 P=”abcabca” P[1+1]T[11] q=PI[1]=0 P=”abcabca” P[0+1]=T[11] q=0+1=1 Knuth-Morris-Pratt KnuthT=”abcabcabcaababcba P=”abcabca• i=12:P[1+1]=T[12] q=1+1=2• i=13:P[2+1]T[13] q=PI[2]=0 P[0+1]=T[13] q=0+1=1 P=”abcabca” T=”abcabcabcaababcba• i=14: P[1+1]=T[14] q=1+1=2• i=15: P[2+1]=T[15] q=2+1=3• i=16: P[3+1]T[16] q=PI[3]=0 P[0+1]T[16] q=0• i=17: P[0+1]=T[17] -> q=0+1=1 Knuth-Morris-Pratt Knuth ánh giá thu t toán:- Thu t toán Knuth-Morris-Pratt có chi phí v th igian là O(m+n) v i nhi u nh t là 2n-1 l n s l n sosánh ký t trong quá trình tìm ki m.THU T TOÁN BOYER-THU TO MOORE Boyer-Moore BoyerÝ tư ng:- Khác v i KMP, thu t toán Boyer-Moore ki m tra các ký t m u t ph i sang trái- Hàm int Last(char c, char*P): Tr v v trí cu i cùng c a c trong m u P. N u c không xu t hi n tr ng P thì tr v -1– Ví d : P= ”abcabdacgj” Last(‘a’,P)=6; Last(‘d’,P)=5; Last(‘p’,P)=-1– D a trên cơ s hàm Last, ta s xây d ng các bư c nh y tăng tính t c Boyer-Moore BoyerThu t toán:– G i s là v trí c n kh o sát. Ban u s=0.– L p ch ng nào s ây là v trí kh p, xu t s. Sau ó d ch ph i bình thư ng(s++)– Trái l i, g i c=T[s+j]. Xét Last(c,P): Boyer-Moore BoyerThu t toán: • TH1: Last(c,P)j. Ta ch d ch ph i 1 v trí (s++) Boyer-Moore BoyerCode:s=0;while (s=0)&&(T[j+s]==P[j])) j--; if (j==-1) { printf(“%d”,s); s++; } else { k=last(T[j+s],P); s=s+ max( j-k,1); }}