BM 01-Bia SKKN



SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI
Trường THPT Chuyên Lương Thế Vinh


Mã số:
(Do HĐKH Sở GD&ĐT
ghi)











SÁNG KIẾN KINH NGHIỆM
TÌM HIỂU HÀM Z TRONG BÀI TOÁN SO KHỚP CHUỖI

Người thực hiện: NGUYỄN HOÀNG ANH

Lĩnh vực nghiên cứu:

- Quản lý giáo dục
- Phương pháp dạy học bộ môn: Tin học
- Lĩnh vực khác: Chuyên đề giảng dạy chuyên tin.


Có đính kèm: Các sản phẩm không thể hiện trong bản in SKKN







Năm học: 2013 - 2014
2
SƠ LƯỢC LÝ LỊCH KHOA HỌC


BM02-
LLKHSKKN


I. THÔNG TIN CHUNG VỀ CÁ NHÂN
- Họ và tên: NGUYỄN HOÀNG ANH
- Ngày tháng năm sinh: 08/09/1987
- Nam, nữ: Nam
- Địa chỉ: 10/8-Tổ 1-Kp1-P Bửu Long- Biên Hòa- Đồng Nai
- Điện thoại: (CQ)/ (NR); ĐTDĐ: 0945 648 411
- Fax: E-mail:
- Chức vụ: Giáo viên
- Đơn vị công tác: Trường THPT Chuyên Lương Thế Vinh
II. TRÌNH ĐỘ ĐÀO TẠO
- Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: Cử nhân
- Năm nhận bằng: 2010
- Chuyên ngành đào tạo: Tin học
III. KINH NGHIỆM KHOA HỌC
- Lĩnh vực chuyên môn có kinh nghiệm: Giảng dạy Tin học
Số năm có kinh nghiệm: 4
- Các sáng kiến kinh nghiệm đã có trong 5 năm gần đây: Không

3

BM03-TMSKKN
Tên SKKN: TÌM HIỂU HÀM Z TRONG BÀI TOÁN SO KHỚP CHUỖI
I. LÝ DO CHỌN ĐỀ TÀI
- Dữ liệu được xử lý thường không phân ra một cách logic thành các mẫu tin độc
lập với các phần nhỏ có thể phân biệt được với nhau. Kiểu dữ liệu này có thể được

đặc trưng duy nhật như một chuỗi (string): đó là một dãy ký tự tuyến tính (có thể
là rất dài).
- Rõ ràng chuỗi là thành phần trung tâm trong các hệ xử lý văn bản, là các hệ cung
cấp nhiều khả năng để thao tác văn bản. Các hệ như vậy xử lý các chuỗi văn bản,
các chuỗi này được định nghĩa một cách “lỏng lẻo” như các dãy chữ, số và ký tự
đặc biệt. Những đối tượng này có thể rất lớn (ví dụ là cuốn sách, tài liệu, tạp chí
), và các thuật toán hiệu quả sẽ đóng một vai trò quan trọng trong việc thao tác
trên các chuỗi đó.
- Một phép toán cơ bản trên chuỗi là so khớp chuỗi (đối sách mẫu) (Pattern
matching hoặc String matching), bài toán được phát biểu ngắn gọn như sau: “Cho
trước một chuỗi văn bản T có độ dài N và một mẫu P có độ dài M, hãy kiểm tra
sự xuất hiện của mẫu P trong văn bản T bao nhiêu lần.”.
- Bài toán so khớp chuỗi có thể được đặc trưng như một bài toán tìm kiếm, trong
đó mẫu được xem như khoá, tuy nhiên các thuật toán tìm kiếm thông thường
không áp dụng một cách trực tiếp vì mẫu có thể dài và do nó trải trên văn bản
theo một cách không biết trước được
- Đã có nhiều thuật toán được đưa ra để giải quyết bài toán này. Một thuật toán
truyền thống như “Brute-force” được sử dụng bằng cách so sánh tuần tự mẫu
trong chuỗi văn bản để tìm ra các vị trí xuất hiện mẫu trong chuỗi. Đây là một
thuật toán đơn giản nhưng thời gian thực hiện luôn tỉ lệ với tích MN.
- Trong năm 1970, S.A.Cook đã chứng minh một kết quả lý thuyết về một loại bài
toán trừu tượng mà nó suy ra sự tồn tại của một thuật toán để giải bài toán so khớp
chuỗi, có thời gian tỉ lệ với M + N trong trường hợp xấu nhất.
- Knuth, Morris và Pratt đã giới thiệu thuật toán của họ vào năm 1976, cùng thời
gian đó R.S.Boyer và J.S.Moore đã khám phá ra một thuật toán nhanh hơn nhiều
trong nhiều ứng dụng. Tuy nhiên thì cả hai thuật toán này được đánh giá là đều
cần đến một chút xử lý phức tạp trên mẫu khiến cho các thuật toán trở nên khó
hiểu do đó hạn chế phạm vi xử dụng của chúng.
- Năm 1980, R.M.Karp và M.O.Rabin đã quan sát thấy rằng bài toán này không
khác lắm so với bài toán tìm kiếm chuẩn như người ta tưởng và đã đi đến một

thuật toán đơn giản gần như thuật toán Brute-force, có thời gian thi hành luôn tỉ
lệ với M + N. Hơn thế nữa, thuật toán của họ mở rộng dễ dàng cho các mẫu và
văn bản 2 chiều, do đó khiên cho nó trỏ nên hữu ích hơn so với các thuật toán còn
lại trong xử lý ảnh.
- Và thuật toán Z được phát triển như là một thuật toán nền tảng cho các thuật toán
so khớp chuỗi sau này.
- Việc phân tích thuật toán để giúp học sinh các lớp chuyên có thể nắm được một
cách cơ bản nhất phương án so khớp chuỗi tốn ít chi phí nhất.


4


II. TỔ CHỨC THỰC HIỆN ĐỀ TÀI
1. Cơ sở lý luận

- Phần “TÌM HIỂU HÀM Z TRONG BÀI TOÁN SO KHỚP CHUỖI” được chọn
dựa trên yêu cầu thực tế cần có một thuật toán dễ tiếp cận và hiệu quả để giải quyết
bài toán SMC trong các đề thi HSG và hệ thống bài tập dành cho học sinh chuyên.
- Các giải thuật hiện tại có chi phí cỡ O(m*n) chưa thực sự đạt hiệu quả cao trong
quá trình so khớp các chuỗi có kích thước lớn.

2. Nội dung, biện pháp thực hiện các giải pháp của đề tài
a. Nội dung
- Phát biểu bài toán so khớp chuỗi trong khoa học máy tính.
- Quá trình hình thành các thuật toán so khớp chuỗi.
- Phân tích thuật toán Z.
- Phân tích quá trình tiền xử lý trong thuật toán.
- Ví dụ minh họa.


b. Biện pháp thực hiện
- Nghiên cứu tài liệu, bài giảng từ internet.
- Hướng dẫn học sinh áp dụng vào các bài tập đặt trưng trong hệ thống bài tập dành
cho học sinh chuyên tin và các bài trong hệ thống thi HSG Tin học.
III. HIỆU QUẢ CỦA ĐỀ TÀI
- Giúp học sinh nắm được và hình thành ý tưởng cho việc áp dụng các thuật toán so
khớp chuỗi trong việc giải quyết các bài toán tương ứng.
IV. ĐỀ XUẤT, KHUYẾN NGHỊ KHẢ NĂNG ÁP DỤNG

-

V. TÀI LIỆU THAM KHẢO

1. Exact String Pattern Recognition - Francisco G´omez Mart´ın
2. Z Algorithm – Codeforces
3. Exact String Matching, Z-Algorithm- www.cs.umd.edu
4. Z Algorithm (JavaScript Demo) -

5. Tài liệu sưu tầm từ Internet
6. Kinh nghiệm giảng dạy của bản thân.



NGƯỜI THỰC HIỆN
(Ký tên và ghi rõ họ tên)
5





SỞ GD&ĐT ĐỒNG NAI
Trường THPT chuyên
Lương Thế Vinh
BM04-
NXĐGSKKN
CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc

Biên Hòa, ngày … tháng … năm 2014

PHIẾU NHẬN XÉT, ĐÁNH GIÁ SÁNG KIẾN KINH NGHIỆM
Năm học: 2013 - 2014
–––––––––––––––––
Tên sáng kiến kinh nghiệm:
TÌM HIỂU HÀM Z TRONG BÀI TOÁN SO KHỚP CHUỖI
Họ và tên tác giả: NGUYỄN HOÀNG ANH - Chức vụ: .Giáo viên

Đơn vị: Trường THPT chuyên Lương Thế Vinh

Lĩnh vực: (Đánh dấu X vào các ô tương ứng, ghi rõ tên bộ môn hoặc lĩnh vực khác)

- Quản lý giáo dục -

- Phương pháp giáo dục - Lĩnh vực khác:



1. Tính mới (Đánh dấu X vào 1 trong 2 ô dưới đây)

- Có giải pháp hoàn toàn mới


- Có giải pháp cải tiến, đổi mới từ giải pháp đã có

2. Hiệu quả (Đánh dấu X vào 1 trong 4 ô dưới đây)

-

- Có tính cải tiến hoặc đổi mới từ những giải pháp đã có và đã triển khai áp dụng trong


-

- Có tính cải tiến hoặc đổi mới từ những giải pháp đã có và đã triển khai áp dụng tại


3. Khả năng áp dụng (Đánh dấu X vào 1 trong 3 ô mỗi dòng dưới đây)

- Cung cấp được các luận cứ khoa học cho việc hoạch định đường lối, chính sách:


- Đưa ra các giải pháp khuyến nghị có khả năng ứng dụng thực tiễn, dễ thực hiện và
dễ đi vào cuộc sống:

- Đã được áp dụng trong thực tế đạt hiệu quả hoặc có khả năng áp dụng đạt hiệu quả
trong phạm vi rộng:


XÁC NHẬN CỦA TỔ CHUYÊN MÔN
(Ký tên và ghi rõ họ tên)
THỦ TRƯỞNG ĐƠN VỊ

(Ký tên, ghi rõ họ tên và đóng dấu)
6



NỘI DUNG ĐỀ TÀI

A. GIỚI THIỆU BÀI TOÁN SO KHỚP CHUỖI: 7
B. QUÁ TRÌNH HÌNH THÀNH CÁC THUẬT TOÁN SO KHỚP CHUỖI: 7
C. THUẬT TOÁN Z - SO KHỚP CHUỖI: 8
I. Giới thiệu: 8
II. Mô tả thuật toán: 8
III. Bước tiền xử lý: 10
IV. Thuật toán tuyến tính 13
V. Tính các giá trị Zi: 13
VI. Kết luận: 17
VII. Một số bài toán có thể ứng dụng hàm Z: 18




7



TÌM HIỂU HÀM Z TRONG BÀI TOÁN SO KHỚP CHUỖI
A. GIỚI THIỆU BÀI TOÁN SO KHỚP CHUỖI:
- Ngay từ giai đoạn sơ khai, bài toán so sánh chuỗi, tìm chuỗi con… là một trong
những bài toán cơ bản của ngành khoa học máy tính.
- Yêu cầu cơ bản của bài toán so chuỗi được phát biểu như sau:

Cho hai chuỗi ký tự:
 A: Chuỗi gốc có n ký tự.
 B: Là chuỗi mẫu [hoặc chuỗi cần tìm kiếm] có m ký tự.
Chuỗi A dài hơn chuỗi B (length (A) ≥ length (B)).
Tìm tất cả các lần xuất hiện của chuỗi mẫu B trong chuỗi gốc A.
- Tuy được nhìn nhận là một trong những bài toán cơ bản và kinh điển của ngành
khoa học máy tính nhưng một ứng dụng thực sự giải quyết được vấn đề trên là
rất hiếm hoi, chúng ta chỉ có thể chỉ ra được sự xuất hiện rất cơ bản của nó trong
các ứng dụng xử lý văn bản mà chúng ta thường dùng hằng ngày.
- Yêu cầu đặt ra trong bài toán này là liệu có thể giải quyết được bài toán trong
thời gian tuyến tính (O (m+n)). Morris và Pratt đã là hai nhà khoa học đầu tiên
giải quyết được bài toán này.
- Các phương pháp tính toán liên quan đến hầu hết tất cả các lĩnh vực, các ứng
dụng dựa trên kỹ thuật so sánh chuỗi [so khớp] trở nên phổ biến và quan trọng.
Trong khoảng cuối của những năm 1980, các yêu cầu tính toán trên số liệu lớn
để phân tích các dữ liệu sinh học ngày càng cấp thiết dẫn đến sự hình thành
ngành Tin-Sinh học. Trong lĩnh vực sinh học, một số kỹ thuật so khớp chuỗi
được sử dụng để phân tích trình tự, tìm gene trong chuỗi AND…. Và còn một
số lĩnh vực khác như Ngành công nghệ Âm nhạc, Xử lý ngôn ngữ, Trí tuệ nhân
tạo, Mắt nhân tạo…cũng ứng dụng các kỹ thuật so khớp chuỗi như một phần
trong hệ thống công cụ nghiên cứu lý thuyết và thực tế.
B. QUÁ TRÌNH HÌNH THÀNH CÁC THUẬT TOÁN SO KHỚP CHUỖI:
- Phương thức đơn giản đầu tiên được áp dụng để so khớp chuỗi là trượt chuỗi
mẫu trên chuỗi gốc và so sánh các ký tự tương ứng với nhau. Thuật toán này
được gọi là thuật toán vét cạn O (mn).
- Các thuật toán về sau được cải tiến từ thuật toán vét cạn, được cải tiến tại một
số bước:
o Thuật toán của Karp-Rabin: cải tiến bước so sánh.
o Thuật toán của Knuth-Morris-Pratt: được cải tiến ở bước trượt mẫu bằng
cách xử lý mẫu trước khi trượt.

o Thuật toán Boyer - Moore: được cải tiến ở bước trượt mẫu bằng cách xử
lý mẫu trước khi trượt và cấu trúc dữ liệu hợp lý giúp cho thuật toán này
đạt được mức thời gian tuyến tính.
8




Các mốc thời gian đánh dấu sự xuất hiện các thuật toán so khớp chuỗi tính đến 2010
C. THUẬT TOÁN Z - SO KHỚP CHUỖI:
I. Giới thiệu:
- Là thuật toán có độ phức tạp tuyến tính được ứng dụng trong các bài toán so
khớp chuỗi. Tuy không phải là thuật toán có độ phức tạp tuyến tính đầu tiên
nhưng lại tương đối dễ hiểu.
- Nhiều thuật toán so khớp cố gắng tránh khỏi số phép dịch lên tới n-m+1 của
thuật toán cổ điển. Để làm được việc đó, một lượng nhỏ thời gian được sử dụng
cho việc phân tích độ phức tạp của xâu mẫu hoặc xâu nguồn đây được gọi là
bước tiền xử lý. Trong các thuật toán của Knut-Morris-Pratt, Boyer-Moore,
Apostolico-Giancarlo thì xâu mẫu được xử lý trước khi thực sự tìm kiếm trong
xâu nguồn. Mặt khác, các phương thức xử lý xâu nguồn lại dựa trên cấu trúc cây
hậu tố.
II. Mô tả thuật toán:
- Khi các phương thứ tiền xử lý được áp dụng nhiều trong nhiều trường hợp hơn
là chỉ nhận diện xâu mẫu, chúng ta chia xây dựng S thành một số xâu tùy ý thay
vì chỉ lấy ra một ký tự P. Cho S là một xâu và i > 1, tại vị trí thứ i, ta giả sử rằng
tất cả các xâu con S[i j] (với i ≤ j ≤ length(S)) là xâu khớp với xâu S[1 j-i+1]
(hay còn gọi là phần tiền tố của xâu S tính đến vị trí thứ j-i+1). Với j là giá trị
lớn nhất có thể có tương ứng với i hiện tại, ta có Z
i
(S) = j

max
–i+1.
Nếu S[i] <> S[1], khi đó hiển nhiên j không tồn tại và Z
i
(S) = 0. Hiểu theo cách
khác, Z
i
(S) được dùng để ghi nhận chiều dài lớn nhất mà S[i i + Z
i
(S) -1] = S[1
Z
i
(S)]. Khi đó, xâu S sẽ được thay thế bằng mảng giá trị Z(S).
Ví dụ:
Cho xâu S = aabadaabcaaba. Bảng giá trị sẽ cho biết trạng thái của mảng Z
i
(S)
của xâu S


9



i
S[i i+Z
i
(S)−1]
S[1 Zi(S)]
Z

i
(S) có là
phần đầu
của S hay
không?
Giá trị thỏa yêu cầu
Z
i
(S)
2
a
a
Yes
1
1
3
b
a
No
0
0
4
a
a
Yes
1
1
5
d
a

No
0
0
6
aab
aab
Yes
{1,2,3}
3
7
a
a
Yes
1
1
8
b
a
No
0
0
9
c
a
No
0
0
10
aaba
aaba

Yes
{1,2,3,4}
4
11
a
a
Yes
1
1
12
b
a
No
0
0
13
a
a
Yes
1
1






Với các giá trị Z
i
(S) dương, ta có một khối Z-boxes các ký tự liên tục bắt đầu từ

i và có kết thúc tại vị trí i +Z
i
-1.

Ứng với giá trị i >1cố định, Gọi:
o r
i
là giá trị lớn nhất trong các vị trí kết thúc của các khối Z
j
với j ≤ i.
o l
i
sau khi xác định được r
i
thì l
i
là giá trị bắt đầu của khối kết thúc tại r
i
.





10



III. Bước tiền xử lý:
- Chúng ta sẽ đi vào chi tiết của thuật toán Z. Khi tính toán giá trị Z

k
, ta chỉ cần
giá trị r
k-1
và l
k-1
. Vì thế, ta có thể đơn giản hóa các ký hiệu để làm cho việc thể
hiện được đơn giản hơn. Thuật toán có thể tính toán nhiều hơn 2 giá trị Z
i
.
- Thuật toán bắt đầu với việc tính toán Z
2
. Theo trình tự, chuỗi con S[1 length(S)]
và S[2 length(S)] sẽ được mang ra so sánh cho đến khi có sự khác biệt. Giá trị
Z
2
có nghĩa là S[1 Z
2
-1]=S[2 Z
2
] và S[1 Z
2
] <> S[2 Z
2
+1]. Sau khi tính Z
2
thuật toán tiếp tục tương tự. Sau khi tính đến giá trị thứ k = Z
k
, tất cả các giá trị
1 k-1 đã được tính toán, ta sẽ phân tích các trường hợp sau:

o k > r: trong trường hợp này ta không thể sử dụng giá trị Z
i
(i<k) để hình
thành khối Z-Box thứ k. Lúc này phải tạo lại một xâu con bắt đầu tại k
cho đến khi gặp kí tự khác nhau. Khi đó, Z
k
là chiều dài của xâu con tìm
được và l=k, r= k+Z
k
-1.

o k<=r: khi đó các giá trị đã tính có thể được sử dụng lại. Khi k<=r, kí tự
thứ k phải thuộc một khối Z-box. Với hai giá trị l và k thì S[k] thuộc
S[l r]. Gọi đoạn S[l r] là A. A là đoạn S[1 Z
l
]. vì thế, ký tự S[k] đương
nhiên sẽ xuất hiện trong đoạn S[1 r-l+1] (lưu ý rằng: Z
l
= r-l+1). Gọi đoạn
S[k r] là B. Đương nhiên B cũng xuất hiện trong đoạn S[1 Z
l
],
B=S[k’ Z
l
]

Sau khi tính được k’, ta có khối Z-box có độ dài Z
k’
gọi là C.


11



Vì thế, nếu ta có hàm tìm chuỗi con có k kí tự tương ứng là phần tiền tố của
S thì ta sẽ nhận được giá trị nhỏ nhất (Z
k’
, |B|) với r-k+1=|B| chính là chiều
dài của B
Phụ thuộc vào min(Z
k’
,|B|) ta có hai trường hợp con:
 Z
k’
< |B|: trong trường hợp này khối Z-box tại k chính là khối tại
k’. Do đó, Z
k
= Z
k’
. Giá trị r và l giữ nguyên.

Ví dụ:
Mô phỏng thuật toán với chuỗi S = aabcdaabcxyaabcdaabcdx
Bảng sau mô tả các giá trị Z
i
, l
i
,r
i
.

12




Ta có 2 định lí:
Định lí 1:
Quá trình tiền xử lý tính toán chính xác tất cả các giá trị Z
i
, l
i
,r
i
.
Định lí 2:
Quá trình tiền xử lý có thời gian là tuyến tính phụ thuộc vào kích thước của xâu S.

13



IV. Thuật toán tuyến tính
-
Thuật toán Z sử dụng trong bài toán so khớp chuỗi được coi là có khả năng thực
hiện trong thời gian và cả không gian tuyến tính O(m+n).

-
Để thực hiện bài toán so khớp hai chuỗi, ta ghép chuỗi A độ dài m và chuỗi B
độ dài n với nhau bằng cách thêm một ký tự # hoặc $ [gọi là ký tự đặc biệt] vào
để được chuỗi S= A$B. Sau khi thực hiện thuật toán Z trên chuỗi S ta sẽ được

các giá trị Z
i
≤ m. Vị trí của ký tự đặc biệt có ảnh hưởng đến kết quả tính toán
của hàm Z. Bất kỳ giá trị Z
i
= m xác định sự xuất hiện của xâu A trong xâu B
tại vị trí i - m - 1

S[i i + Zi- 1] = S[i i + m - 1] = T[i - m - 1 i - 1] = S[1 m]=P[1 m]

Trong trường hợp đảo thứ tự khi ghép, khi tìm thấy A trong B tại vị trí i, hàm Z
sẽ trả về giá trị Z
m+1+I
= m.
Ví dụ:
Cho xâu P=aab m=3 xâu T= abcaaabxy  n=9
Ta được xâu S như sau: S= P$T = aab$abcaabxy
Ta có bảng giá trị sau:

Theo bảng trên, xâu P xuất hiện tại vị trí thứ 8-3-1=4 trong xâu T.
V. Tính các giá trị Zi:
Dựa trên một cách tiếp cận khác, kỹ thuật KMP (Knuth–Morris–Pratt) chỉ ra rằng có
thể giải quyết các bài toán dạng này trong với độ phức tạp O (k+m).  tưởng thuật toán
như sau:
Cho xâu S = ABC ABCDAB ABCDABCDABDE
Cho xâu P = ABCDABD
Ở mỗi bước trượt xâu P trên xâu S, ta so sánh tuần tự các kí tự tương ứng cho đến khi
gặp kí tự không phù hợp  ta trượt đến một vị trí thích hợp có khả năng phù hợp để so
khớp tiếp và có thể bỏ qua một số ký tự ta chắc chắn rằng không có khả năng cho kết quả
phù hợp.

1 2
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: 0123456
Trong ví dụ trên ta thấy rằng tại vị trí S[3] = ‘ ‘ và P[3]=’D’ không phù hợp nên việc so
khớp tại bước này phải dừng lại. Tiếp đến, thay vì bắt đầu so khớp tại vị trí S[1] ta bỏ qua
14



vì S[1]=’B’ <> P[0]=A  sai ngay từ bước so khớp đầu tiên  thừa. Tương tự cho các vị
trí từ 23. Ta tiếp tục tại vị trí S[4]


1 2
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: 0123456
ở bước 2, đoạn được khớp là ABCDAB, đến S[9] = ‘ ‘ <> P[6]=’D’ nên ngừng so khớp.
Ở đây ta chú ý: S[4 9] =’ABCDAB’ có S[8]=’A’ = P[0] nên vị trí tiếp theo được xét sẽ
là S[8]
tương tự ta có các bước thực hiện như sau:
1 2
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: 0123456
1 2

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: 0123456
1 2
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: 0123456
Kết quả chuỗi P xuất hiện tại vị trí 15 trong S.
Dựa trên ý tưởng của thuật toán KMP, thuật toán Z là thuật toán cải tiến của KMP có
nhiệm vụ tính ra một giá trị đặc trưng của mỗi kí tự trong S để sử dụng trong các bước so
sánh.
15



Ứng dụng tính gi tr Z
i
:

Cho xâu S, Z
i
[S]=k là chiều dài chuỗi con lớn nhất bắt đầu từ i đến i+k sao cho S[1 k]=
S[i i+k]
VD: cho xâu S = aabcaabxaaz, ta được các giá trị Z như sau:
Z
1
=0; Z
2

=1; Z
3
=0; Z
4
=0; Z
5
=3; Z
6
=2; Z
7
=0; Z
8
=0; Z
9
=2; Z
10
=1; Z
11
=0
Để ứng dụng trong bài toán so khớp chuỗi, ta có thể dễ dàng nhận thấy:
Đầu tiên ta phải tạo xâu S=P$T ($ là kí tự chắc chắn không xuất hiện trong P và T )
Sau đó tạo các giá trị Z
i
của xâu S nếu tồn tại Z
i
[S] >= |P| thì xâu P xuất hiện trong xâu
T.
Trong quá trình tính toán các giá trị Z
I
tư tưởng của thuật toán Z là hạn chế các phép so

khớp chuỗi không cần thiết dựa trên các nhận xét sau:
- Z
i
= r
i
– i trong đó r
i
là vị trí kết thúc của xâu con xuất phát từ i.
- Gọi r = max(r
i
) (i=1 n) là giá trị phải nhất. l là giá trị tương ứng với r.
- Ứng với mỗi Z
k
(k=1 n) ta xét 2 trường hợp:
o k>r: ta duyệt so khớp chuỗi như thông thường để tính giá trị Z
k
tương ứng
ta có giá trị l
k
và r
k
tương ứng. Cập nhật lại r
max
và l
rmax

o k<=r :






- Gọi K là vị trí đang xét, trong trường hợp K < r
max
thì ta có l
rmax
<= k <= r
max
.
- r
max
- K = 𝛽
- Xét:
o Z
k’
< 𝛽: Ta có Z
k’
= Z
K

o Z
k’
> 𝛽: Z
k
= 𝛽
o Z
k’
= 𝛽:







S
X
Y
𝛼
𝛼
r
max
l
rmax
𝐾
𝐾’
𝛽
𝛽
S
Rmax-Lmax
S
0
S
X
Y
r
max
l
rmax
𝐾
𝐾’

𝛽
𝛽
S
Rmax-Lmax
S
0
𝛼
𝛼
𝛽
Z
16



Ta thấy rõ ràng trong trường hợp này Y # Z.
Vấn đề còn lại là so sánh X và Y.
Nếu X#Y: Z
K
= 𝛽
Nếu X=Y: Z
K
= 𝛽 + |𝑋 ∩ 𝑌 |
(Với |𝑋 ∩ 𝑌 | là số kí tự tương ứng khớp nhau của 2 chuỗi X và Y ở các vị
trí tương ứng trên hình.)
Ý nghĩa của Z
i
:
Trong bài toán so khớp chuỗi, ta cần tìm vị trí xuất hiện của xâu P trong xâu T. Từ giá trị
Z
i

ta được các thông tin sau:
- Z
i
- cho biết độ khớp của vị trí hiện tại với xâu mẫu.
- Z
i
= |P| có nghĩa là P xuất hiện tại vị trí thứ i trong T.
- Số lượng các Z
i
= |P| cho biết số lần xuất hiện P trong T.
Từ đó cho phép ta kết luận bài toán và tính toán các thông số liên quan mà không cần tốn
quá nhiều phép so sánh chuỗi thừa.



17



VI. Kết luận:
- Hàm Z có thể giải quyết bài toán SMC trong thời gian tuyến tính một cách đơn
giản nhưng hiệu quả. Có thể nó chưa giải quyết được hầu hết các trường hợp
nhưng với hướng tiếp cận này, nó đã mở ra một hướng giải quyết vô cùng lý
tưởng cho các bài toán bài toán SMC kinh điển và hiện đại.

18



VII. Một số bài toán có thể ứng dụng hàm Z:

1. So khớp
McFn rất thích các trò chơi với xâu ký tự. Anh tìm ra một thuật toán có thể hữu
ích trong các bài toán so khớp chuỗi.
Cho xâu S(n) và i (i=1, 𝑛), gọi F(i) là đoạn dài nhất chứa phần hậu tố chung của
xâu S và xâu S[1 i] . Ví dụ: xâu S = zaaxbaacbaa, khi đó F(1) = 0, F(2)=1, F(3)=2,
F(4)=0, , F(10)=1, F(11)=11.
Ta xem xâu S[1 n] là hậu tố của chính nó.
Yêu cầu: Cho xâu S(n) và số nguyên i (i=1, 𝑛), tính
F(i)
Dữ liệu:
Input:
- Dòng đầu tiên chứa số nguyên T là số lượng
test.
- Với mỗi test:
o Dòng thứ 2 chứa xâu S, chỉ chứa ký tự thường,
có độ dài không quá 10
6

o Dòng tiếp theo là số K, là số lượng các đoạn con
cần tính.
o Dòng thứ i trong K dòng tiếp theo chứa số x
(1 <= x <= len(S))
Output:
- Với mỗi số x được cho, tính F(x). Mỗi số ghi
trên một dòng.
2. Palindrome Degree
Xâu S(n) được gọi là xâu K-Palindrome nếu xâu đó là xâu Palindrome. Và xâu
tiền tố và hậu tố của xâu S có độ dài n/2 cũng là xâu palindrome. Theo định
nghĩa trên thì xâu rỗng là xâu 0-palindrome
Gọi ‘độ palindrome’ của xâu S là giá trị lớn nhất của k

để xâu S là xâu palindrome. Ví dụ, xâu S=”abaaba” có
k=3
Yêu cầu: cho xâu S, tính tổng tất cả các ‘độ palindrome’
k của các xâu tiền tố của xâu S
Dữ liệu:
Input:
- Chứa duy nhất xâu S không rỗng, chứa cả chữ và số có độ dài không quá
5*10
6
.
Output:
- Số duy nhất là tổng của các ‘độ palindrome’ k của các xâu tiền tố của xâu
S.

input
output
1
zaaxbaacbaa
11
1
2
3
4
5
6
7
8
9
10
11

0
1
2
0
0
1
3
0
0
1
11


input
output
a2A
1
abacaba
6
19



3. Băng giấy
Cho hai băng giấy ghi hai xâu X và Y. Xâu Y có độ dài nhỏ hơn xâu X. Các ký tự
trên băng giấy có thể được dịch chuyển sang trái hay sang phải một số ký tự tạo
thành xâu xoay vòng.
Ví dụ: xâu X= ‘abc’  dịch sang trái 1 ký tự thì ta có xâu X = ‘bca’, …
Hai xâu X và Y được gọi là tương đồng nếu sau một số a lần dịch chuyển trên xâu
X và một số b lần dịch chuyển trên xâu Y ta có:

- Xâu Y chính là phần tiền tố của xâu X
- Xâu Y sai khác chỉ một ký tự so với phần tiền tố của X
Ví dụ:
 Cho xâu X= ‘KADAABRA’, Y=’ABRA’ . Sau khi dịch chuyển xâu X sang trái
4 lần thì ta có xâu Y là phần đầu của xâu X=’ABRAKADA’
 Cho xâu X= ‘KADDDBRA’, Y=’ABRA’. Sau khi dịch chuyển xâu X sang trái
4 lần thì ta có xâu Y khác phần đầu của xâu X=’DBRAKADA’ chỉ một ký tự


Yêu cầu: Xuất ra trạng thái của xâu X và Y để xâu X và Y là xâu tương đồng sau
một số lần dịch chuyển cả hai xâu.
Dữ liệu:
Input:
Chứa hai xâu X, Y độ dài không quá 10
6
.
Output:
Hai xâu X,Y sau khi dịch chuyển và đang
trong trạng thái tương đồng. Nếu có nhiều
lựa chọn thì thứ tự ưu tiên lựa chọn như
sau :
- Chọn phương án có số lần dịch chuyển xâu X là ít nhất.
- Chọn phương án có số lần dịch chuyển sang phải ít nhất.

sample input
sample output
7 4
KADABRA
ABRA
AABR

DABRAKA