Chuyện gì sẽ xảy ra khi so sánh 2 chuỗi năm 2024

Tùy chọn. Xác định kiểu so sánh chuỗi. Nếu so sánhtham đối là null, lỗi xảy ra. Nếu so sánh được bỏ qua, tùy chọn so sánh thiết đặt sẽ xác định kiểu so sánh.

Thiết đặt

Các thiết đặt so sánh đối số là:

Hằng số

Giá trị

Mô tả

vbBinaryCompare

0

Thực hiện so sánh nhị phân.

so sánh vbtext

1

Thực hiện so sánh văn bản.

vbDatabaseCompare

2

chỉMicrosoft Office Access 2007. Thực hiện so sánh dựa trên thông tin trong cơ sở dữ liệu của bạn.

Giá trị trả về

Hàm Strcomp có các giá trị trả về sau:

If

Trả về strcomp

string1 nhỏ hơn string2

-1

string1 bằng string2

0

string1 lớn hơn string2

1

string1 hoặc string2 là null

Null

Ví dụ về truy vấn

Biểu thức

Kết quả

CHỌN ProductSales. ProductID, StrComp (ProductID, "PRO_XYZ10") như ComparisonResult từ ProductSales;

Trả về các giá trị từ trường "ProductID", so sánh các giá trị trong "ProductID" với "PRO_XYZ1" và trả về kết quả trong sánh theo cột. "ProductID" bằng "PRO_XYZ10", hàm StrComp sẽ trả về 0. Nếu "ProductID" nhỏ hơn "PRO_XYZ10", hàm StrComp sẽ trả về-1. Nếu "ProductID" lớn hơn "PRO_XYZ10", hàm StrComp sẽ trả về 1. Nếu một trong hai "ProductID" hoặc "PRO_XYZ10" là NULL, hàm StrComp sẽ trả về NULL.

Ví dụ về VBA

Lưu ý: Các ví dụ sau thể hiện cách sử dụng hàm này trong mô-đun Visual Basic for Applications (VBA).

Ví dụ này sử dụng hàm Strcomp để trả về kết quả so sánh chuỗi. Nếu đối số thứ ba là 1, thì một so sánh văn bản được thực hiện; Nếu đối số thứ ba là 0 hoặc bỏ qua, một so sánh nhị phân được thực hiện.

________0

Bạn cần thêm trợ giúp?

Bạn muốn xem các tùy chọn khác?

Khám phá các lợi ích của gói đăng ký, xem qua các khóa đào tạo, tìm hiểu cách bảo mật thiết bị của bạn và hơn thế nữa.

Cộng đồng giúp bạn đặt và trả lời các câu hỏi, cung cấp phản hồi và lắng nghe ý kiến từ các chuyên gia có kiến thức phong phú.

Thuật toán so khớp chuỗi Knuth–Morris–Pratt (hay thuật toán KMP) tìm kiếm sự xuất hiện của một "từ"

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1 trong một "xâu văn bản"

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

2 bằng cách tiếp tục quá trình tìm kiếm khi không phù hợp, bản thần "từ"

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1 cho ta đầy đủ thông tin để xác định vị trí bắt đầu của ký tự so sánh tiếp theo, do đó bỏ qua quá trình kiểm tra lại các ký tự đã so sánh trước đó.

Thuật toán được Donald Knuth, Vaughan Pratt và James H. Morris nghiên cứu độc lập năm 1977, nhưng họ công bố nó cùng nhau.

Thuật toán KMP[sửa | sửa mã nguồn]

Ví dụ cho thuật toán tìm kiếm[sửa | sửa mã nguồn]

Để minh họa chi tiết thuật toán, chúng ta sẽ tìm hiểu từng quá trình thực hiện của thuật toán. Ở mỗi thời điểm, thuật toán luôn được xác định bằng hai biến kiểu nguyên,

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

4 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

5, được định nghĩa lần lượt là vị trí tương ứng trên

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

2 bắt đầu cho một phép so sánh với

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1, và chỉ số trên

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1 xác định ký tự đang được so sánh. Khi bắt đầu, thuật toán được xác định như sau:

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

Chúng ta tiến hành so sánh các ký tự của

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1 tương ứng với các ký tự của

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

2, di chuyển lần lượt sang các chữ cái tiếp theo nếu chúng giống nhau.

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

1 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

2 đều là ‘A’. Ta tăng i:

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

3 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

4 đều là ‘B’. Ta tiếp tục tăng i:

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

5 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

6 đều là ‘C’. Ta tăng i lên 3:

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

Nhưng, trong bước thứ tư, ta thấy

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

7 là một khoảng trống trong khi

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

8, không phù hợp. Thay vì tiếp tục so sánh lại ở vị trí

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

3, ta nhận thấy rằng không có ký tự

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

0 xuất hiện trong khoảng từ vị trí 0 đến vị trí 3 trên xâu

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

2 ngoài trừ vị trí 0; do đó, nhờ vào quá trình so sánh các ký tự trước đó, chúng ta thấy rằng không có khả năng tìm thấy xâu dù có so sánh lại. Vì vậy, chúng ta di chuyển đến ký tự tiếp theo, gán

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

2 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

3.

m: ____4 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

Tiếp tục quá trình so sánh như trên, ta xác định được xâu chung

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

4, với

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

5 (

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

6), ta lại thấy không phù hợp. Nhưng từ kết quả của quá trình so sánh trước, ta đã duyệt qua

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

7, có khả năng sẽ là khởi đầu cho một đoạn xâu khớp, vì vậy ta bắt đầu so sanh từ vị trí này. Như chúng ta đã thấy các ký tự này đã trùng khớp với nhau ký tự trong phép so khớp trước, chúng ta không cần kiểm tra lại chúng một lần nữa; ta bắt đầu với

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

8,

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

9 và tiếp tục quá trình so khớp.

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

Quá trình so khớp ngay lập tức thất bại, nhưng trong

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1 không xuất hiện ký tự

m: ____4 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

1,vì vậy, ta tăng

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

4 lên 11, và gán

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

3.

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

Một lần nữa, hai xâu trùng khớp đoạn ký tự

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

4 nhưng ở ký tự tiếp theo,

m: ____4 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

5, không trùng với

m: ____4 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

6 trong

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1. Giống như trước, ta gán

m: ____4 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

8, và gán

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

9, và tiếp tục so sánh.

m: _`i` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

Lần này, chúng ta đã tìm được khớp tương ứng với vị trí bắt đầu là

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

0.

Thuật toán và mã giả của thuật toán tìm kiếm[sửa | sửa mã nguồn]

Bây giờ, chúng ta tìm hiểu về sự tồn tại của bảng "so khớp một phần"(partial match)

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

1, được mô tả bên dưới, giúp ta xác định được vị trí tiếp theo để so khớp khi phép so khớp trước đã thất bại. Mảng

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

1 được tổ chức để nếu chúng ta có một phép so khớp bắt đầu từ

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

3 thất bại khi so sánh

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

4 với

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

5, thì vị trí của phép so khớp tiếp theo có chỉ số là

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

6 trong

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

2 (

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

8 là đại lượng xác định số ô cần lùi khi có một phép so khớp thất bại). Mặc dù phép so khớp tiếp theo sẽ bắt đầu ở chỉ số

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

6, giống như ví dụ ở trên, chúng ta không cần so sánh các ký tự

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

8 sau nó, vì vậy chúng ta chỉ cần tiếp tục so sánh từ ký tự

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

1. Ta có

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

2, cho thấy rằng nếu

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

2 không khớp, ta không phải lùi lại mà tiếp tục phép so sánh mới ở ký tự tiếp theo. Sau đây là đoạn mã giả mẫu của thuật toán tìm kiếm KMP.

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

Độ phức tạp của thuật toán tìm kiếm[sửa | sửa mã nguồn]

Với sự xuất hiện của mảng

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

1, phần tìm kiếm của thuật toán Knuth–Morris–Pratt có độ phức tạp

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

5, trong đó

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

6 là độ dài của xâu

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

2. Ngoại trừ các thủ tục nhập xuất hàm ban đầu, tất cả các phép toán đều được thực hiện trong vòng lặp

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

8, chúng ta sẽ tính số câu lệnh được thực hiện trong vòng lặp; để làm được việc này ta cần phải tìm hiểu về bản chất của mảng

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

1. Theo định nghĩa, mảng được tạo để: nếu một phép so khớp bắt đầu ở vị trí

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

3 thất bại khi so sánh

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

4 với

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

5, thì phép so khớp có thể thành công tiếp theo sẽ bắt đầu ở vị trí

m: _`i` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

3. Cụ thể hơn, phép so khớp tiếp theo sẽ bắt đầu tại vị trí có chỉ số cao hơn

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

4, vì vậy

m: _`i` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

5.

Từ điều này, chúng ta thấy rằng vòng lặp có thể thực hiện

m: _`i` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

6 lần. Với mỗi lần lặp, nó thực hiện một trong hai nhánh của vòng lặp. Nhánh thứ nhất tăng

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

5 và không thay đổi

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

4, vì vậy chỉ số

m: _`i` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

9 của ký tự đang so sánh trên

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

2 tăng lên. Nhánh thứ hai cộng thêm

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

1 vào

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

4, và như chúng ta đã biết, đây luôn là số dương. Vì vậy, vị trí

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

4, vị trí bắt đầu của một phép so khớp tiềm năng tăng lên. Vòng lặp dừng nếu

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

4; vì vậy mỗi nhánh của vòng lặp có thể được sử dụng trong tối đa

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

6 lần, do chúng lần lượt tăng giá trị của

m: _`i` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

9 hoặc

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

4, và

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

8: nếu

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

9, thì

algorithm kmptable: input:

mảng ký tự, W 
mảng số nguyên, T 

output:

mảng T

define variables:

biến kiểu nguyên, pos ← 2 
biến kiểu nguyên, cnd ← 0 

let T[0] ← -1, T[1] ← 0 while pos nhỏ hơn độ dài của W, do:

(trường hợp một: tiếp tục dãy con)
**if** W[pos - 1] = W[cnd],   

 **let** T[pos] ← cnd + 1, pos ← pos + 1, cnd ← cnd + 1
(trường hợp hai: không thỏa mãn, nhưng ta có thể quay ngược trở lại)
**otherwise**, **if** cnd > 0, **let** cnd ← T[cnd]
(trường hợp ba: hết phần tử. Chú ý rằng cnd = 0)
**otherwise**, **let** T[pos] ← 0, pos ← pos + 1

0, vì vậy: do các phép toán chủ yếu tăng theo đơn vị, chúng ta đã có

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

4 vào một thời điểm nào đó trước, và vì vậy thuật toán dừng.

Do đó vòng lặp chủ yếu thực hiện

m: _`i` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

6 lần, độ phức tạp tính toán của thuật toán tìm kiếm chỉ là

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

5.

Bảng so sánh một phần ("Partial match")[sửa | sửa mã nguồn]

Mục đích của bảng là cho phép thuật toán so sánh mỗi ký tự của

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

2 không quá một lần. Sự quan sát chìa khóa về bản chất của phương pháp tìm kiếm tuyến tính cho phép điều này xảy ra là trong quá trình so sánh các đoạn của chuỗi chính với đoạn mở đầu của mẫu, chúng ta biết chính xác được những vị trí mà đoạn mẫu có thể xuất hiện trước vị trí hiện tại. Nói cách khác, chúng ta "tự tìm kiếm" đoạn mẫu trước và đưa ra một danh sách các vị trí trước đó mà bỏ qua tới các ký tự vô vọng mà vẫn không mất đi các đoạn tiềm năng.

Chúng ta muốn tìm kiếm, với mỗi vị trí trên

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1, độ dài của đoạn dài nhất giống với "đoạn bắt đầu" trên

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1 tính đến (không bao gồm) vị trí đó, đây là khoảng cách chúng ta có thể lùi lại để tiếp tục so khớp. Do vậy

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

8 là giá trị của độ dài đoạn dài nhất kết thúc bởi phần tử

algorithm kmptable: input:

mảng ký tự, W 
mảng số nguyên, T 

output:

mảng T

define variables:

biến kiểu nguyên, pos ← 2 
biến kiểu nguyên, cnd ← 0 

let T[0] ← -1, T[1] ← 0 while pos nhỏ hơn độ dài của W, do:

(trường hợp một: tiếp tục dãy con)
**if** W[pos - 1] = W[cnd],   

 **let** T[pos] ← cnd + 1, pos ← pos + 1, cnd ← cnd + 1
(trường hợp hai: không thỏa mãn, nhưng ta có thể quay ngược trở lại)
**otherwise**, **if** cnd > 0, **let** cnd ← T[cnd]
(trường hợp ba: hết phần tử. Chú ý rằng cnd = 0)
**otherwise**, **let** T[pos] ← 0, pos ← pos + 1

8. Chúng ta sử dụng quy ước rằng một chuỗi rỗng có độ dài là 0. Với trường hợp không trùng với mẫu ngay ở giá trị đầu tiên (không có khả năng lùi lại), ta gán

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

2.

Ví dụ cho thuật toán xây dựng bảng[sửa | sửa mã nguồn]

Ta xét xâu

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

00. Ta sẽ thấy thuật toán xây dựng bảng có nhiều nét tương đồng với thuật toán tìm kiếm chính. Ta gán

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

2. Để tính

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

02, ta cần tìm ra một xâu con

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

03 đồng thời cũng là xâu con bắt đầu của

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1. Vì vậy ta gán

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

05. Tương tự,

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

06 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

07.

Ta xét đến ký tự

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

08,

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

0. Dễ thấy ký tự này trùng với ký tự bắt đầu xâu

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

2. Nhưng do

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

8 là độ dài xâu dài nhất trùng với xâu con bắt đầu trong

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1 tính đến

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

13 nên

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

14 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

15. Tương tự, ký tự

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

16 trùng với ký tự

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

4 nên

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

18.

Vì vậy ta có bảng sau:

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

5 0 1 2 3 4 5 6

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

5 A B C D A B D

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

8 -1 0 0 0 0 1 2

Một ví dụ khác phức tạp hơn

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

5 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

5 P A R T I C I P A T E I N P A R A C H U T E

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

8 -1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 3 0 0 0 0 0

Mã giả của thuật toán tạo bảng[sửa | sửa mã nguồn]

Ví dụ ở trên đã mô tả kỹ thuật tổng quát để tạo bảng.

Dưới đây là đoạn mã giả

algorithm kmptable: input:

mảng ký tự, W 
mảng số nguyên, T 

output:

mảng T

define variables:

biến kiểu nguyên, pos ← 2 
biến kiểu nguyên, cnd ← 0 

let T[0] ← -1, T[1] ← 0 while pos nhỏ hơn độ dài của W, do:

(trường hợp một: tiếp tục dãy con)
**if** W[pos - 1] = W[cnd],   

 **let** T[pos] ← cnd + 1, pos ← pos + 1, cnd ← cnd + 1
(trường hợp hai: không thỏa mãn, nhưng ta có thể quay ngược trở lại)
**otherwise**, **if** cnd > 0, **let** cnd ← T[cnd]
(trường hợp ba: hết phần tử. Chú ý rằng cnd = 0)
**otherwise**, **let** T[pos] ← 0, pos ← pos + 1

Độ phức tạp của thuật toán tạo bảng[sửa | sửa mã nguồn]

Độ phức tạp của thuật toán tạo bảng là

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

25, với

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

26 là độ dài của

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1. Ngoại trừ một số sắp xếp ban đầu, toàn bộ công việc được thực hiện trong vòng lặp

m: _`W` S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0

8, độ phức tạp của toàn bộ vòng lặp là

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

25, với việc cùng lúc xử lý giá trị của

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

30 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

31. Trong trường hợp thứ nhất,

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

31 không thay đổi, khi cả

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

30 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

34 cùng tăng lên một đơn vị. Ở trường hợp hai,

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

34 được thay thế bởi

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

36, như chúng ta đã biết ở trên, luôn luôn nhỏ hơn

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

34, do đó tăng giá trị của

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

31. Trong trường hợp thứ ba,

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

30 tăng và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

34 thì không, nên cả giá trị của

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

30 và

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

31 đều tăng. Mà

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

43, điều này có nghĩa là ở mỗi bước hoặc

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

30 hoặc chặn dưới

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

30 đều tăng; mà thuật toán kết thúc khi

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

46, nên nó phải kết thúc tối đa sau

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

47 vòng lặp, do

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

31 bắt đầu với giá trị

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

49. Vì vậy độ phức tạp của thuật toán xây dựng bảng là

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

25.

Độ phức tạp của thuật toán KMP[sửa | sửa mã nguồn]

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

0

Như đã thấy trong ví dụ ở trên, thuật toán mạnh hơn các thuật toán so khớp chuỗi kém hơn vì nó có thể bỏ qua các ký tự đã duyệt. Ít ô phải quay trở lại hơn, thuật toán sẽ nhanh hơn, và được thể hiện trong bảng

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

1 bởi sự hiện diện của các số không. Một từ như

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

52 sẽ làm tốt với thuật toán này vì nó không có sự lặp lại của những chữ bắt đầu, vì vậy mảng đơn giản chỉ toàn số không với -1 ở đầu. Ngược lại, với từ

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

53 nó hoạt động tồi tệ, bởi vì bảng sẽ là

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

5 0 1 2 3 4 5 6

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

5 A A A A A A A

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

8 -1 0 1 2 3 4 5

Đây là mẫu xấu nhất cho mảng

m:

algorithm kmpsearch: input:

mảng ký tự, S (đoạn văn bản)
mảng ký tự, W (xâu đang tìm)

output:

một biến kiểu nguyên (vị trí (bắt đầu từ 0) trên S mà W được tìm thấy)

define variables:

biến nguyên, m ← 0 
biến nguyên, i ← 0 
mảng nguyên, T 

while m + i nhỏ hơn độ dài của sâu S, do:

**if** W[i] = S[m + i],
  **let** i ← i + 1
  **if** i bằng độ dài W,
    **return** m
**otherwise**,
  **if** T[i] > -1,
    **let** i ← T[i], m ← m + i - T[i]
  **else**
    **let** i ← 0, m ← m + 1

return độ dài của đoạn văn bản S

S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: __2

1, và nó có thể dùng để so sánh với đoạn như

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

58, trong trường hợp này thuật toán sẽ cố gắng ghép tất cả các chữ

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: ___3

0 với 'B' trước khi dừng lại; kết quả là số lượng tối đa câu lệnh được sử dụng, tiến tới trên hai lần số ký tự của xâu S khi số lần lặp của

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

60 tăng. Mặc dù quá trình xây dựng bảng rất nhanh so với chữ này (nhưng vô tác dụng), quá trình này chạy có một lần với chữ

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1, trong khi quá trình tìm kiếm chạy rất nhiều lần. Nếu với mỗi lần, từ

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

1 được dùng để tìm trên xâu như xâu

m: 0 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: _1

2, độ phức tạp tổng thể sẽ rất lớn. Bằng cách so sánh, sự kết hợp này là trường hợp tốt nhất với thuật toán so khớp chuỗi Boyer-Moore.

Lưu ý rằng trong thực tế, thuật toán KMP làm việc không tốt đối với tìm kiếm trong văn bản ngôn ngữ tự nhiên, bởi vì nó chỉ có thể bỏ qua các ký tự khi phần đầu của từ giống với một phần trong văn bản. Trong thực tế điều này chỉ đôi khi xảy ra trong các văn bản ngôn ngữ tự nhiên. Ví dụ, hãy xem xét bao nhiêu lần một xâu "text" xuất hiện trong đoạn văn này.