Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 5: Chuỗi ký tự

ùi được so trùng thành công với phần tương ứng của s. Được như vậy thì i mới 
hoàn toàn không phải lùi lại. Trong lần so trùng mới, chính si này sẽ được so 
sánh với aj, với j sẽ được tính toán thích hợp mà chúng ta sẽ bàn đến sau. Trong 
ví dụ chúng ta thấy j = 2, lần so sánh đầu tiên của lần so trùng thứ hai là so sánh 
giữa s4 và a2. 
Tương tự, khi lần so trùng thứ hai thất bại tại s8, chuỗi con a sẽ được dịch chuyển 
rất xa, tiết kiệm được rất nhiều lần so trùng. Chúng ta dễ dàng kiểm chứng, với 
những vị trí trung gian khác, phần đầu của a không trùng với phần cuối (chỉ tính 
phần màu xám) của a, nên cũng không thể trùng với phần tương ứng trên s, có 
thực hiện so trùng cũng sẽ thất bại mà thôi. 
• 
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
s 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1
a 1 0 1 0 0 1 1 1 
 a 1 0 1 0 0 1 1 1 
 a 1 0 1 0 0 1 1 1 
 a 1 0 1 0 0 1 1 1 
 a 1 0 1 0 0 1 1 1 
Hình 5.3- Minh họa giải thuật Knuth-Morris-Pratt 
Bắt đầu lần so trùng thứ hai 
 (i = 4, j = 2) 
Bắt đầu lần so trùng thứ ba 
(i = 8, j = 1) 
Chương 5 – Chuỗi ký tự 
Giáo trình Cấu trúc dữ liệu và Giải thuật 86
Hình vẽ dưới đây giúp chúng ta hiểu được cách tính chỉ số j thích hợp cho đầu 
mỗi lần so trùng (trong khi i không lùi về mà giữ nguyên để tiếp tục tiến tới). 
Trích từ hình vẽ trên, chúng ta có được kết quả sau đây. 
Xét vị trí i = 4, j = 4, do so sánh si với aj thất bại, chúng ta đang muốn biết 
phần cuối của a kể từ điểm này trở về trước (tức chỉ tính phần màu xám) và phần 
đầu của a trùng được bao nhiêu ký tự. Gọi a’ = a. Chúng ta sẽ nhìn quét từ cuối 
phần màu xám của a và từ đầu của a’, chúng ta sẽ biết được có bao nhiêu ký tự 
trùng. Đó là hai ký tự 1 và 0 được gạch dưới. 
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
s 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 
a 1 0 1 0 0 1 1 1 
a’ 1 0 1 0 0 1 1 1 
Như vậy, điều này hoàn toàn không còn phụ thuộc vào s nữa. Chúng ta có thể 
tính số ký tự trùng theo j dựa trên a và a’. Đồng thời ta thấy số ký tự trùng này 
cũng là chỉ số mà j phải lùi về cho lần so trùng kế tiếp aj với si, i không đổi. 
Chúng ta bắt đầu với j = 1 và xem hình 5.4 sau đây. 
j=4, số ký tự trùng là 2
i 
Chương 5 – Chuỗi ký tự 
Giáo trình Cấu trúc dữ liệu và Giải thuật 87
a 1 0 1 0 0 1 1 1 next1 = 0 
a’ 1 0 1 0 0 1 1 1 
a 1 0 1 0 0 1 1 1 next2 = 0 
a’ 1 0 1 0 0 1 1 1 
a 1 0 1 0 0 1 1 1 next3 = 1 
a’ 1 0 1 0 0 1 1 1 
a 1 0 1 0 0 1 1 1 next4 = 2 
a’ 1 0 1 0 0 1 1 1 
a 1 0 1 0 0 1 1 1 next5 = 0 
a’ 1 0 1 0 0 1 1 1 
a 1 0 1 0 0 1 1 1 next6 = 1 
a’ 1 0 1 0 0 1 1 1 
a 1 0 1 0 0 1 1 1 next7 = 1 
a’ 1 0 1 0 0 1 1 1 
Hình 5.4- Minh họa giải thuật Knuth-Morris-Pratt 
 Giả sử chúng ta đã tạo được danh sách next mà phần tử thứ j chứa trị mà j 
phải lùi về khi đang so sánh aj với si mà thất bại (aj ≠ si), để bắt đầu lần so trùng 
kế tiếp (i giữ nguyên không đổi). Hình 5.4 cho thấy next1 luôn bằng 0 với mọi a. 
Chúng ta có giải thuật KMP-Search như dưới đây. 
Lần so trùng thứ nhất luôn bắt đầu từ ký tự đầu của s và a, nên hai chỉ số i và 
j đều là 0. 
• Trường hợp dễ hiểu nhất là trong khi mà aj=si thì i và j đều được nhích 
tới. Điều kiện dừng của vòng lặp hoàn toàn như giải thuật Brute-Force 
trên, có nghĩa là j đi được hết chiều dài của a (tìm thấy a trong s), hoặc i đi 
quá chiều dài của s (việc tìm kết thúc thất bại). 
j=1, số ký tự trùng là 0 (khi đếm số ký tự trùng, luôn phải dịch chuyển a’ sang 
phải so với a, tức chỉ so sánh phần cuối của a với phần đầu của a’, trường hợp 
này xem như không có ký tự trùng). 
j=2, số ký tự trùng là 0 
j=3, số ký tự trùng là 1 
j=4, số ký tự trùng là 2 
j=5, số ký tự trùng là 0 
j=6, số ký tự trùng là 1 
j=7, số ký tự trùng là 1 
Chương 5 – Chuỗi ký tự 
Giáo trình Cấu trúc dữ liệu và Giải thuật 88
• Trường hợp aj≠si (với j≠0) trong một lần so trùng nào đó thì như đã nói 
ở trên, chỉ việc cho j lùi về vị trí đã được chứa trong phần tử thứ j trong 
danh sách next. Nhờ vậy trong lần lặp kế tiếp sẽ tiếp tục so sánh aj này 
với si mà i không đổi. 
• Riêng trường hợp đặc biệt, với j = 0 mà aj≠si, ta xem hình dưới đây 
s  1 1 0 0 1 0 0 1 1 1 0 1 1 
 a 1 0 1 0 0 1 1 1 
Bất cứ một lần so sánh si nào đó với a0 mà thất bại thì chuỗi a cũng phải dịch 
chuyển sang phải một bước, để lần so sánh kế tiếp (cũng là lần so trùng mới) có 
thể so sánh a0 với si+1. Như vậy ta chỉ cần tăng i và giữ nguyên j mà thôi. 
j=0, số ký tự trùng là 0
i
// Giải thuật Knuth- Morris – Pratt 
int strstr(const String &s, const String &a); 
/* 
post: Nếu a là chuỗi con của s, hàm trả về vị trí xuất hiện đầu tiên của a trong s; 
ngược lại, hàm trả về -1. 
*/ 
{ 
 List next; 
 int i = 0, // Chỉ số chạy trên s. 
 j = 0, // Chỉ số chạy trên a. 
 ls = s.strlen(); // Số ký tự của s. 
 la = a.strlen(), // Số ký tự của a. 
 const char* pa = a.c_str(); //Địa chỉ ký tự đầu tiên của a. 
 const char* ps = s.c_str(); //Địa chỉ ký tự đầu tiên của s. 
 InitNext(a, next); // Khởi gán các phần tử next1, next2,,nextla-1. 
 // Không sử dụng next0. 
 do { 
 if (pa[j]==ps[i]){// Vẫn còn ký tự trùng trong một lần so trùng 
 i++; // nào đó, i và j được quyền nhích tới. 
 j++; 
 } 
 else 
 if (j == 0) // Đây là trường hợp đặc biệt, phải dịch a sang phải 
i++; // một bước, có nghĩa là cho i nhích tới. 
 else 
 next.retrieve(j, j); // Cho j lùi về trị đã chứa trong nextj. 
 } while ((j<la) && (i<ls)); 
 if (j>=la) return i – la; 
 else return –1; 
} 
Chương 5 – Chuỗi ký tự 
Giáo trình Cấu trúc dữ liệu và Giải thuật 89
Sau đây chúng ta sẽ viết hàm InitNext gán các trị cho các phần tử của 
next, tức là tìm số phần tử trùng theo hình vẽ 5.4. Có một điều khá thú vị trong 
giải thuật này, đó chính là hàm tạo danh sách next lại sử dụng ngay chính danh 
sách này. Chúng ta thấy rằng để tìm số phần tử trùng như đã nói, chúng ta cần 
dịch chuyển a’ về bên phải so với a, mà việc dịch chuyển a’ trên a cũng hoàn 
toàn giống như việc dịch chuyển a trên s trong khi đi tìm a trong s. 
Hàm tạo next được chép lại từ giải thuật KMP-Search trên, chỉ có vài điểm 
bổ sung như sau: với i chạy trên a và j chạy trên a’, và a’ luôn phải dịch phải 
so với a, chúng ta khởi gán i=1 và j=0. 
Do i tăng đến đâu là chúng ta xem như đã so trùng xong phần cuối của a (kể 
từ vị trí i này trở về trước) với phần đầu của a’, nên nexti đã được xác định. 
Trong quá trình so trùng, trong khi mà ai vẫn còn bằng a’j, i và j đều nhích 
tới. Vì vậy, chúng ta dễ thấy rằng j chính là số phần tử đã trùng được của a’ so 
với a, chúng ta có phép gán nexti=j. 
// Hàm phụ trợ gán các phần tử cho danh sách next. 
void InitNext(const String &a, List &next); 
/* 
post: Gán các trị cho các phần tử của next dựa trên chuỗi ký tự a. 
*/ 
{ 
 int i = 1, // Chỉ số chạy trên a. 
 j = 0, // Chỉ số chạy trên a’. 
 la = a.strlen(), // Số ký tự của a (cũng là của a’). 
 const char* pa = a.c_str(); //Địa chỉ ký tự đầu tiên của a (cũng là của a’). 
 next.clear(); 
 next.insert(1, 0); // Luôn đúng với mọi a. 
 do { 
 if (pa[j]==pa[i]){ // Vẫn còn ký tự trùng trong một lần so trùng 
 i++; // nào đó, i và j được quyền nhích tới. 
 j++; // Từ vị trí i trên a trở về trước, j xem như đã 
 next.insert(i, j);// quét được số phần tử trùng của a’ so với a. 
 } 
 else 
 if (j == 0){ // Trường hợp đặc biệt, phải dịch a sang phải 
 i++; // một bước, có nghĩa là cho i nhích tới. 
 next.insert(i, j); 
 }; 
 else 
 next.retrieve(j, j); // Cho j lùi về trị đã chứa trong nextj. 
 } while (i<la); // i=la là đã gán xong la phần tử của next, 
// không sử dụng next0. 
} 
Chương 5 – Chuỗi ký tự 
Giáo trình Cấu trúc dữ liệu và Giải thuật 90
Khi ai ≠ a’j, chúng ta sử dụng ý tưởng của KMP-Search là cho j lùi về 
nextj. Vấn đề còn lại cần kiểm chứng là giá trị của nextj phải có trước khi nó 
được sử dụng. Do chúng ta đã gán vào nexti và đã sử dụng nextj, mà i luôn luôn 
đi trước j, nên chúng ta hoàn toàn yên tâm về điều này. 
Cuối cùng, chỉ còn một điều nhỏ mà chúng ta cần xem xét. Đó là trường hợp có 
nhiều phươg án cho số ký tự trùng nhau. Chẳng hạn với a là “10101010111” và 
j=8, số ký tự trùng khi dịch a’=a về bên phải so với a là: 
a 1 0 1 0 1 0 1 0 1 1 1... Số ký tự trùng là 6 
a’ 1 0 1 0 1 0 1 0 1 1 1... 
a 1 0 1 0 1 0 1 0 1 1 1... 
a’ 1 0 1 0 1 0 1 0 1 1 1... Số ký tự trùng là 4 
a 1 0 1 0 1 0 1 0 1 1 1... 
a’ 1 0 1 0 1 0 1 0 1 1 1... Số ký tự trùng là 2 
Sinh viên hãy tự suy nghĩ xem cách chọn phương án nào là đúng đắn nhất và 
kiểm tra lại các đoạn chương trình trên xem chúng có cần phải được sửa đổi gì 
hay không. 
Ngoài ra, giải thuật KMP-Search còn có thể cải tiến một điểm nhỏ, đó là 
trước khi gán nexti=j trong InitNext, chúng ta kiểm tra nếu paj=pai thì sẽ 
gán nexti=nextj. Do khi so trùng pai mà thất bại thì có lùi về panexti=paj cũng 
sẽ thất bại, chúng ta nên lùi hẳn về panextj. 
Số lần so sánh tối đa trong KMP-Search là ls+la. 
Vị trí j đang xét