V â Minh P hæ – Bæ m«n K hoa häc m¸ y tÝnh
1
CHUỖI VÀ CÁC BÀI TOÁN TRÊN CHUỖI
Chuỗi (string) là một loại dữ liệu cơ bản thường được sử dụng trong rất nhiều
các hệ thống và là thành phần cơ bản trong các hệ thống xử lý văn bản (word-
processing-system), các hệ thống này cung cấp cho ta rất nhiều khả năng để xử
lý văn bản. Ngoài ra một vài các hệ thống đồ hoạ trên máy tính (computer
graphics system) biểu diễn các hình ảnh như là các chuỗi nhị phân.
Các thao tác trên chuỗi chúng ta thường gặp một số các phép toán cơ bản như:
- Phép tìm kiếm một chuỗi con trong một chuỗi.
- Phép thay thế một chuỗi con của một chuỗi bởi một chuỗi khác.
- Phép chen chuỗi con vào một chuỗi.
- Phép loại bỏ một chuỗi con của một chuỗi.
Trong các phép toán nêu trên thì phép tìm kiếm trên chuỗi là phép toán quan
trọng và thường gặp , vì vậy ta chỉ tìm hiểu các giải thuật liên quan đến phép
toán này đó là :
1. Giải thuật Brute-Force.
2. Giải thuật Knuth-Morris-Pratt.
3. Giải thuật Boyer-Moore.
$1. Các khái niện cơ bản về chuỗi
1.1. Chuỗi và phân chia chuỗi
a. Định nghĩa chuỗi
Chuỗi là một dãy các ký tự được chứa trong một vùng liên tục của bộ nhớ. Các
ký tự này có thể là ký tự chữ, ký tự số hoặc ký tự đặc biệt.
Chuỗi ký tự (text string) có thể được xem như là dãy các chữ, các số và các ký
tự đặc biệt.
Một loại chuỗi khác là chuỗi nhị phân (binary string), đó là một dãy các kí tự 0
và 1.
V â Minh P hæ – Bæ m«n K hoa häc m¸ y tÝnh
2
b. Độ dài chuỗi. Số ký tự của chuỗi được gọi là chiều dài của chuỗi. Mỗi ký tự
chiếm 1 byte.
Một chuỗi có thể có chiều dài bằng 0 gọi là chuỗi rỗng(null string ), ký hiệu là “
Một chuỗi có thể được chia làm nhiều phần, mỗi phần là một chuỗi con (sub
string ). Các chuỗi con có thể có chiều dài bằng nhau hoặc khác nhau.
1.2. Cách phân chia chuỗi
a. Dùng ký tự đặc biệt. Dùng ký tự trống ( blank) để phân chia chuỗi con. Khi đó
các chuỗi con có thể khác nhau. Để truy xuất một chuỗi con trong chuỗi thì ta
phải tìm kiếm từ đầu chuỗi. Do đó tốc độ truy xuất của phương pháp này chậm.
b. Dùng chiều dài cố định. Ta chia các chuỗi con thành các phần bằng nhau. Để
truy xuất một chuỗi con trong một chuỗi thì ta dùng công thức tính địa chỉ. Do
đó tốc độ truy xuất của phương pháp này rất nhanh.
c. Dùng chỉ điểm (pointer).
- Dùng chỉ điểm đầu: Chỉ điểm đầu chỉ vào ký tự đầu tiên của chuỗi con.
Ta sử dụng biến Last để cho biết địa chỉ của ký tự cuối cùng của chuỗi.
Gọi:
n- số chuỗi con
ai-địa chỉ của ký tự đầu tiên của chuỗi con thứ i
bi- địa chỉ của ký tự cuối cùng của chuỗi con thứ i
Ta có :
ai = pointer[i]
bi = pointer[i+1]-1 , nếu i<n
= last , nếu i=n
- Dùng chỉ điểm cuối : Chỉ điểm cuối chỉ vào ký tự cuối cùng của chuỗi
con. Ta sử dụng biến First để cho biết địa chỉ của ký tự đầu tiên của
chuỗi.
Ta có :
ai = First , nếu i=1
V â Minh P hæ – Bæ m«n K hoa häc m¸ y tÝnh
3
= pointer[i-1] ,nếu i>1
bi = pointer[i]
$2.Các giải thuật tìm kiếm trê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[i]
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[i] = p[j] thì ta tăng chỉ số i và j lên 1(xét đến ký tự tiếp theo)
Nếu a[i]<>p[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 hoặc i>n.
- Ta khai báo :
Type
St =string[255];
V â Minh P hæ – Bæ m«n K hoa 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[i]=p[j] then
begin
i:=i+1;
j:=j+1;
V â Minh P hæ – Bæ m«n K hoa 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