Thuật toán Knutt - Morris - Pratt

Tham khảo tài liệu thuật toán knutt - morris - pratt, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Thuật toán Knutt - Morris - PrattPlease purchase apersonal license. personalTHU T TOÁN KNUTT-THU TO MORRIS-PRATT String matching StringBài toán:- Tìm v trí xu t hi n u tiên c a chu i con trong 1 o n text- Tìm v trí xu t hi n ti p theo b ng cách thay i giá tr u c a o n text- Thu t toán thông thư ng: - So sánh kí t u c a o n text và kí t u c a chu i con - N u trùng so sánh kí t ti p theo - N u khác so sánh tăng kí t o n text - Quá trình ti p di n cho n khi h t chu i con String matching StringThu t toán: isub= 0; itext = 0; //ví tr hi n t i c a chu i và o n text starttext=0; //v trí b t u while (itext String matching String ánh giá thu t toán: - m – strlength c a substring - n - strlength c a o n text S l n so sánh trong trư ng h p x u nh t: m*(t-m+1)Ví d : substring (AA….AAB), text(AA…AAA) Substring có m-1 A, text có n A Dn n trư ng h p x u nh t Knuth-Morris-Pratt KnuthÝ tư ng: d mô t ,ta coi các xâu ánh s t 1.–– Xâu W g i là ti n t (prefix) c a xâu X n u X có d ng WY (Y là 1 xâu nào ó)– VD: X=“qetyughjk” W=“qety”– Xâu W g i là h u t (suffix) c a xâu X n u X có d ng YW (Y là 1 xâu nào ó)– VD: X=”qetyughjk” W=”yughjk”– N u có thêm W# X thì W g i là prefix(hay suffic) th c s c a X. Knuth-Morris-Pratt KnuthÝ tư ng:– Hàm int Prefix(int q): tr dài c a prefix dài nh t c a P[1..m] ng th i là suffix th c s c a P[1..q]. VD: P=“abcabcd” Prefix(1)=0 P=“abcabcd” Prefix(2)=0 P=“abcabcd” Prefix(3)=0 P=“abcabcd” Prefix(4)=1 P=“abcabcd” Prefix(5)=2 P=“abcabcd” Prefix(6)=3 P=“abcabcd” Prefix(7)=0 Knuth-Morris-Pratt KnuthVí d :1. P=”abc abc” Prefix(6)=3.2. P=”abcababcabc” Prefix(11)=33. P=”abcabcabcaa” Prefix(11)=14. P=”abcababcabd” Prefix(11)=0 Knuth-Morris-Pratt KnuthThu t toán tính Prefix:PI [1]= 0 ; k=0;for (q=2;q0 && P[k+1] P[q]) k=PI[k]; if(P[k+1]==P[q]) k++; PI[q]=k;} Knuth-Morris-Pratt KnuthThu t toán tính KMP:– Xác nh dài q c a xâu v a là prefix c a P,v a là suffix c a T[1..i] v i i = 1->n.– N u q=m thì v trí kh p chính là i-m+1. Cách tính q g n như cách tính Prefix. q=0 for (i=1;i0 && P[q+1]T[i]) q=PI[q]; if (P[q+1]==T[i]) q++; if (q==m) {printf(“%d”, i-m+1);q=PI[q]} }