Bài toán tìm kiếm xâu mẫu
3 posters
Trang 1 trong tổng số 1 trang
Bài toán tìm kiếm xâu mẫu
Khắc phục: tính toán theo modul (p,t tính theo số dư khi chia cho 1 số q nàođó).Tuy nhiên như vậy dẫn đến 1 số xâu khác nhau vẫn có thể cho các số giốngnhau.Vì vậy khi tìm được số t=p, ta phải kiểm tra xem vị trí đó có thật sự làkhớp hay không. Nên chọn q đủ lớn,<= Max_nguyên / k 4.
Thuật toán Knuth-Morris-Pratt:
Ý 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.
Hàm int Prefix(int q):Hàm trả độ dài của prefix dài nhất của P[1..m] đồng thời là suffix thực sự củaP[1..q].VD: P=”abcabcd”P=”abcabcd” -> Prefix(1)=0P=”abcabcd” -> Prefix(2)=0P=”abcabcd” -> Prefix(3)=0P=”a bca bcd” -> Prefix(4)=1P=”abcab cd” -> Prefix(5)=2P=”abcabc d” -> Prefix(6)=3P=”abcabcd” -> Prefix(7)=0Ta xây dựng PI(k)=Prefix(k) với k=1->m:+ Dễ thấy PI[1]=0.+ Giả sử đã có các PI(k) với mọi k<q.Ta sẽ tính PI(q).
VD1
: P=”abcabc” q=6P=”abcab c” -> PI(5)=2Khi bổ sung kí tự P[3], ta thấy nó khớp với “ab” thành “abc” là suffic củaxâu P[1..6]: P=”abcabc ”Vậy PI(6)=PI(5)+1=3.
VD2
: P=”abcababcabc” q=11P=”abcababcab c” -> PI(10)=5Khi bổ sung kí tự P[6], ta thấy nó ghép với “abcab” thành “abcaba” không phải là suffic của xâu P[1..11]. Nhưng xâu Prefix của “abcab” (tức “ab”) thì khớp với kí tự tiếp theo(P[3]=”c”) tạo thành xâu “abc” chính là suffic của P[1..11]P=”abcababcabc ” -> PI(11)=3
VD3
: P=”abcabcabcaa” q=11P=”abcabca bca a” -> PI(10)=7Khi bổ sung kí tự P[8] ,ta thấy nó ghép với “abcabca” thành “abcabcab”không phải là suffic của xâu P[1..11].Xét xâu Prefix của “abcabca” (tức “abca”).Nó ghép với kí tự tiếp theo(P[5]=”b”) tạo thành xâu “abcab” vẫn không là suffic của P [1..11]
Xét xâu tiếp Prefix của “abca” (tức “a”).Nó ghép với kí tự tiếp theo(P[2]=”b”) tạo thành xâu “ab” vẫn không là suffic của P [1..11]Xét xâu tiếp Prefix của “a” là “”.Nó ghép với kí tự tiếp theo(P[1] =”a”) tạothành xâu “a” là suffic của P [1..11].V ậy: PI(11)=1. (Bạn có thể tự kiểm tra)
VD4
: P=”abcababcabd” q=11P=”abcababcab d” -> PI(10)=5Khi bổ sung kí tự P[6] ,ta thấy nó ghép với “abcab” thành “abcaba” không phải là suffic của xâu P[1..11].Xét xâu Prefix của “abcab” (tức “ab”).Nó ghép với kí tự tiếp theo(P[3 ]=”c”) tạo thành xâu “abc” vẫn không là suffic của P [1..11]Xét xâu Prefix của “abc”(tức “”).Nó ghép với kí tự tiếp theo(P[1]=”a”) tạothành xâu “a” vẫn không là suffic của P [1..11]V ậy PI(11)=0. Từ đó ta có thuật toán tính Prefix:1. PI [1]= 0 ; k=0;2. for (q=2;q<=m;q++)while ((k>0) && (P[k+1]<>P[q]))k=PI[k]if (P[k+1]== P[q]) k++PI[q]=k;
Thuật toán: Dựa trên hàm Prefix nêu trên ta có thuật toán tìm kiếm xâu mẫu:Ý tưởng là 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. Ta thấy rằng 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.1.q=02.for i=1 to nwhile q>0 and P[q+1]<>T[i]q=PI[q]if P[q+1]==T[i] then q++if q==m thenOUTPUT(i-m+1)q=PI[q]VD: T=”abcabcabcaababcba” P=”abcabca”P=”abcabca” -> PI[1]=0P=”abcabca” -> PI[2]=0P=”abcabca” -> PI[3]=0P=”a bca bca” -> PI[4]=1P=”abcab ca” -> PI[5]=2P=”abcabc a” -> PI[6]=3P=”abca bca ” -> PI[7]=4q=0
i=1: T=”a bcabcabcaababcba” P[0+1]=T[1] -> q=0+1=1P=”a bcabca”i=2: T=”abcabcabcaababcba” P[1+1]=T[2] -> q=1+1=2P=”abcabca”i=3: T=”abcabcabcaababcba” P[2+1]=T[3] -> q=2+1=3P=”abcabca”i=4: T=”abca bcabcaababcba” P[3+1]=T[4] -> q=3+1=4P=”abca bca”i=5: T=”abcabcabcaababcba” P[4+1]=T[5] -> q=4+1=5P=”abcabca”i=6: T=”abcabcabcaababcba” P[5+1]=T[6] -> q=5+1=6P=”abcabca”i=7: T=”abcabca bcaababcba” P[6+1]=T[7] -> q=6+1=7 ->
Xuất s=1
P=”abcabca” q=PI[7]= 4->P=”abca bca”i=8: T=”abcabcabcaababcba” P[4+1]=T[8] -> q=4+1=5P=”abcabca”i=9: T=”abcabcabcaababcba” P[5+1]=T[9] -> q=5+1=6P=”abcabca”i=10: T=”abcabcabcaababcba” P[6+1]=T[10] -> q=6+1=7 ->
Xuất s=4
P=”abcabca”->P=”abca bca”i=11: T=”abcabcabcaababcba” P[4+1]<>T[11] -> q=PI[4]=1P=”a bcabca” P[1+1]<>T[11] -> q=PI[1]=0P[0+1]=T[11] -> q=0+1=1i=12: T=”abcabcabcaababcba” P[1+1]=T[12] -> q=1+1=2P=”abcabca”i=13: T=”abcabcabcaababcba” P[2+1]<>T[13] -> q=PI[2]=0P=”a bcabca” P[0+1]=T[13] -> q=0+1=1i=14: T=”abcabcabcaababcabca” P[1+1]=T[14] -> q=1+1=2P=”abcabca”i=15: T=”abcabcabcaababcba” P[2+1]=T[15] -> q=2+1=3P=”abcabca”i=16: T=”abcabcabcaababcba” P[3+1]<>T[16] -> q=PI[3]=0P=”abcabca” P[0+1]<>T[16] -> q=0i=17: T=”abcabcabcaababcba” P[0+1]=T[17] -> q=0+1=1P=”a bcabca
Độ phức tạp:O(m+n
Re: Bài toán tìm kiếm xâu mẫu
trông cậu quen quen t cũng làm đề nè có gì giúp vs nhé
vithiendi- Tổng số bài gửi : 4
Join date : 21/11/2011
Hay
Cậu này nhìn khá quen. Cảm ơn vì những gì cậu đã post lên 4rum cho mọi nguwoif nhé. .
Tớ thấy đề tài của cậu khá hay. Nếu có thể Post lên cho mọi nguwoif cùng tham khảo
Tớ thấy đề tài của cậu khá hay. Nếu có thể Post lên cho mọi nguwoif cùng tham khảo
Mr.Mad- Tổng số bài gửi : 10
Join date : 23/11/2011
Re: Bài toán tìm kiếm xâu mẫu
t học CN CNTT4 còn cậu
vithiendi- Tổng số bài gửi : 4
Join date : 21/11/2011
Re: Bài toán tìm kiếm xâu mẫu
hnay t thấy bạn rồi
làm bt thế nào rồi
làm bt thế nào rồi
vithiendi- Tổng số bài gửi : 4
Join date : 21/11/2011
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|