Download miễn phí Chuỗi và các bài toán trên chuỗi



Phân tích giải thuật
Trường hợp xấu nhất của giải thuật này là trường hợp cả hai chuỗi p và a đều
gồm các số 0 và kết thúc là số 1. Khi đó với n-m +1 lần tìm kiếm ta phải so sánh
m ký tự của chuỗi p với các ký tự tương ứng của chuỗi a.
Số lần so sánh :
Cmax=m*(n-m+1)
Ta có thể cải tiến giải thuật này bằng giải thuật Knuth- Morris-Pratt.


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-02-11-chuoi_va_cac_bai_toan_tren_chuoi.bMGq10qoar.swf /tai-lieu/de-tai-ung-dung-tren-liketly-58864/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

ên chuỗi
Bài toán: Tìm kiếm chuỗi p có chiều dài là m trong chuỗi a có chiều dài n.
Có hai trường hợp xảy ra sau khi tìm kiếm đó là:
- Nếu không tìm thấy chuỗi p trong chuỗi a thì kết quả là 0.
- Nếu tìm thấy chuỗi p trong chuỗi a thì kết quả là vị trí của ký tự đầu tiên
của lần tìm thấy đầu tiên.
Sau đây chúng ta lần lượt đi vào phân tích từng giải thuật cụ thể :
2.1. Giải thuật Brute- Force.
a. Nội dung của giải thuật
- Đối với vị trí kí tự thứ i của chuỗi a (i=1,2,…,n-m+1) ta so sánh các ký tự
tương ứng từ trái qua phải:
p[1] với a
p[2] với a[i+1]
………….
p[m] với a[i+m+1]
- Gọi:
i - chỉ số của chuỗi a.
j - chỉ số của chuỗi p.
Nếu a = p[j] thì ta tăng chỉ số i và j lên 1(xét đến ký tự tiếp theo)
Nếu ap[j] thì ta cho j chỉ về đầu chuỗi p (j=1) và i chỉ về vị trí ký tự
kế tiếp khi bắt đầu tìm kiếm lần cuối cùng (i = i-j+2).
Giải thuật kết thúc khi j>m hay i>n.
- Ta khai báo :
Type
St =string[255];
Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 4
Index = 1..255;
c. Giải thuật:
Chương trình thực hiện giải thuật này như sau:
program Brute_Force;
uses crt;
type
st=string[50];
var a,p:st; {a chứa chuỗi nguồn , p là chuỗi đích, n độ dài chuỗi a ,m là độ dài chuỗi
p}
procedure init;
var i,j:integer;
begin
writeln('Nhập chuỗi a:');
readln(a);
writeln('Nhập chuỗi p:');
readln(p);
end;
procedure Result;
begin
writeln('Chuỗi cần tìm là:',p)
end;
Function Brutesearch(p,a:st):integer;
var i,j,m,n:integer;
begin
m:=length(p);
n:=length(a);
i:=1;
j:=1;
repeat
if a=p[j] then
begin
i:=i+1;
j:=j+1;
Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 5
end
else
begin
i:=i-j+2;
j:=1;
end;
until(j>m)or (i>n);
if j>m then Brutesearch:=i-m;
else Brutesearch:=0;
end;
begin
clrscr;
Init;
Brutesearch(a,p);
write('Vị trí của ký tự đầu của chuỗi p trong a là:',Brutesearch(p,a):2);
writeln;
Result;
readln;
end.
Ví dụ: Ta xét một ví dụ cụ thể sau:
Cho chuỗi a=’ 0101101001110011101011100’ n=27, chuỗi p=’ 010011’ m=6
stt So sánh 2 giá trị Chí số mới của i và j Chú thích
1 a[1]=p[1] i=2;j=2
2 a[2]=p[2] i=3;j=3
3 a[3]=p[3] i=4;j=4
4 a[4]p[4] i=2,j=1 i=i-j+2
5 a[2]p[1] i=3;j=1 -
6 a[3]=p[1] i=4;j=2 Tăng i và j lên 1
7 a[4]=p[2] i=5;j=3 -
8 a[5]p[3] i=4;j=1 i=i-j+2
Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 6
9 a[4]p[1] i=5;j=1 -
10 a[5]p[1] i=6;j=1 -
11 a[6]=p[1] i=7;j=2 tăng i và j lên 1
12 a[7]=p[2] i=8;j=3 -
13 a[8]=p[3] i=9;j=4 -
14 a[9]=p[4] i=10;j=5 -
15 a[10]=p[5] i=11;j=6 -
16 a[11]=p[6] i=12;j=7 giải thuật kết thúc do
j>m
Đến đây giải thuật kết thúc giá trị trả về ở đây là 6 của lần tìm thấy đầu tiên
a=’ 0101101001110011101011100’
p=’ 010011’
d. Phân tích giải thuật
Trường hợp xấu nhất của giải thuật này là trường hợp cả hai chuỗi p và a đều
gồm các số 0 và kết thúc là số 1. Khi đó với n-m +1 lần tìm kiếm ta phải so sánh
m ký tự của chuỗi p với các ký tự tương ứng của chuỗi a.
Số lần so sánh :
Cmax=m*(n-m+1)
Ta có thể cải tiến giải thuật này bằng giải thuật Knuth- Morris-Pratt.
2.2. Giải thuật Knuth- Morris- Pratt.
a. Nội dung của giải thuật
- Trong giải thuật Brute-Force ta nhận thấy khi so sánh đến ký tự p[j]a thì
ta đã có j -1 kí tự đầu tiên của chuỗi p bằng với các j-1 ký tự cuối cùng trước a
của chuỗi a.
Ví dụ :
Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 7
chuỗi a là :’1010100111’
chuỗi p là :’10100111‘
- Ta nhận thấy a[5] và p[5] khác nhau. Khi đó ta không cần cho j=1 nữa mà cho
j về 3 để so sánh vì ta nhận thấy 3 ký tự đầu tiên của chuỗi p bằng với 3 ký tự
đang xét cuối cùng của của chuỗi a. Do đó ta không cần cho i quay về vị trí
trước nữa mà vẫn tiếp tục cho i tăng. Ta sử dụng mảng next[1…m] để để ghi
nhận giá trị j quay về . Phần tử next[j] sẽ cho giá trị mới của j khi phát hiện hai
ký tự khác nhau. Mảng next[1…m] được xác định như sau :
- Sử dụng chuỗi p1 hoàn toàn giống p.
Cho chuỗi p1 di chuyển từ trái qua phải đồng thời so sánh với chuỗi p và dừng
lại khi các kí tự đầu tiên của chuỗi p1 trùng với các kí tự của chuỗi p. Các kí tự
trùng này sẽ xác định giá trị của next.
- Nếu sự khác nhau này được phát hiện ở p[j] thì next[j] :=1+số ký tự trùng nhau
+.với j=1 next[j]=0
+.với j>1 next[j] := lµ sè lín nhÊt k<j sao cho k-1 ký tù ®Çu tiªn cña p1 trïng
víi k-1 ký tù cuèi cïng cña j-1 (t¹i thêi ®iÓm ®ang xÐt) ký tù ®Çu tiªn cña p.
- Khi x¸c ®Þnh next [j] viÖc di chuyªn p1 qua ph¶i dõng l¹i khi ph¸t hiÖn c¸c ký tù
®i tr­íc cña chuçi p1 trïng víi c¸c ký tù cña chuçi p hoÆc khi p1[1]=p[j].
- Khi xác định next[j] việc di chuyển chuỗi p1 qua phải sẽ dừng lại khi phát hiện
các kí tự đi trước của chuỗi p1 bằng với các kí tự của chuỗi p hay khi p1[1] gặp
p[j].
b. Giải thuật :
program Knuth_Morris_Pratt;
uses crt;
type
st=string[50];
Index=1..50;
var a,p:st;{a chứa chuỗi nguồn, p là chuỗi đích;n là độ dài của a;m la độ dài của
p}
Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 8
procedure init;
var i,j:integer;
begin
writeln('Nhập chuỗi a:');
readln(a);
writeln('Nhập chuỗi p:');
readln(p);
end;
procedure Result;
begin
writeln('Chuỗi cần tìm là:',p);
end;
Function Kmsearch(p,a:st):integer;
var i,j,m,n:integer;
next:array[index]of integer;
procedure Initnext;
begin
i:=1;
j:=0;
next[1]:=0;
repeat
if(j=0)or(p=p[j])then
begin
i:=i+1;
j:=j+1;
next:=j;
end;
else
j:=next[j];
Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 9
until i=m;
end;
begin
m:=length(p);
n:=length(a);
{Tạo mảng next}
Initnext;
i:=1;
j:=1;
repeat
if (j=0) or (a=p[j]) then
begin
i:=i+1;
j:=j+1;
end;
else
begin
j:=next[j];
end;
until(j>m)or (i>n);
if j>m then Kmsearch:=i-m
else Kmsearch:=0;
end;
begin
clrscr;
Init;
Kmsearch(a,p);
write('Vị trí của ký tự đầu của chuỗi p trong a là:',Kmsearch(p,a):2);
writeln;
Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 10
Result;
readln;
end.
c. Ví dụ cụ thể
Cho chuỗi a : 101'01.0'011'1 i =10
p : 101'00.1'11 j =8
Các bước sẽ được thể hiện trong bảng sau :
j next[j] chuỗi
2 1 101’001’11 (p)
101’001’11 (p1)
3 1 101’001’11
101’001’11
4 2 101’001’11
101’001’11
5 3 101’001’11
1 01’001’11
6 1 101’001’11
1 01’001’11
7 2 101’001’11
1 01’001’11
8 101’001’11
101’001’11
Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 11
Số lần so sánh Cmax=n+m. Ta thấy số lần so sánh đã giảm đi nhiều lần.
2.3. Giải thuật Boyer –Moore
a. Nội dung giải thuật:
- Giải thuật Boyer-Moore tương tự với giải thuật Knuth-Morris-Pratt. Đối với
giải thuật Boyer, ta xét chuỗi p1 từ phải qua trái trong khi ta so sánh chuỗi p với
chuỗi a.
Cách xây dựng mảng next của giải thuật Boyer-Moore là phần tử next[j] là số vị
trí kí tự mà chuỗi p sẽ di chuyển qua phải đối với chuỗi p1 để có được vị trí khác
nhau ở kí tự thứ j kể từ phải qua trái của chuỗi p.
b. Giải thuật:
Để xác định vị trí mới của j khi có sự so sánh trùng nhau ta dùng mảng skip.
Hàm Function Ord(c:char):integer trả về số thứ tự của ký tự c trong bộ ký tự
(đánh số từ 1).
Khi đó skip[c]=m nếu c không phải là một ký tự của chuỗi p
skip[c]=m-j nếu c là kí tự thứ j của chuỗi p.
Ta có giải thuật :
Program Boyer-Moore;
Use crt;
Type
St=string[50];
Const
Charno=255;
procedure init;
begin ...

---

Yêu cầu Download