Bài toán tìm kiếm xâu mẫu

**Admin** Sun Nov 13, 2011 11:11 pm

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