Thuật toán so khớp chuỗi Knuth-Morris-Pratt

Thuật toán Knuth–Morris–Pratt

Bách khoa toàn thư mở Wikipedia

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ừ" W trong một "xâu văn bản"S bằng cách tiếp tục quá trình tìm kiếm khi không phù hợp, chính từ 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à J. H. Morris nghiên cứu độc lập năm 1977, nhưng họ công bố nó cùng nhau.

Mục lục   [ẩn]  1 Thuật toán KMP 1.1 Ví dụ cho thuật toán tìm kiếm 1.2 Thuật toán và mã giả của thuật toán tìm kiếm 1.3 Độ phức tạp của thuật toán tìm kiếm 2 Bảng so sánh một phần ("Partial match") 2.1 Ví dụ cho thuật toán xây dựng bảng 2.2 Mã giả của thuật toán tạo bảng 2.3 Độ phức tạp của thuật toán tạo bảng 3 Độ phức tạp của thuật toán KMP 4 Liên kết ngoài 5 Chú thích

[sửa]Thuật toán KMP

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

Để 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 và i, được định nghĩa lần lượt là vị trí tương ứng trên S bắt đầu cho một phép so sánh với W, vàchỉ số trên W 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 W tương ứng với các kí tự của S, di chuyển lần lượt sang các chữ cái tiếp theo nếu chúng giống nhau. S[0] và W[0] đều là ‘A’. Ta tăng i :

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

S[1] và W[1] đều là ‘B’. Ta tiếp tục tăng i :

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

S[2] và W[2] đề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 S[3] là một khoảng trống trong khi W[3] = 'D', không phù hợp. Thay vì tiếp tục so sánh lại ở vị trí S[1], ta nhận thấy rằng không có kí tự 'A' xuất hiện trong khoảng từ vị trí 0 đến vị trí 3 trên xâu S 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 = 4 và i = 0.

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 "ABCDAB", với W[6] (S[10]), 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 "AB", 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 hau 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 = 8, i = 2 và tiếp tục quá trình so khớp.

m: ________8
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 W không xuất hiện kí tự ‘ ‘,vì vậy, ta tăng m lên 11, và gán i = 0.

m:         ___________11
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ự "ABCDAB" nhưng ở kí tự tiếp theo, 'C', không trùng với 'D' trong W. Giống như trước, ta gán m = 15, và gán i = 2, và tiếp tục so sánh.

m:         _______________15
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à S[15].

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

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) T, đượ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 T được tổ chức để nếu chúng ta có một phép so khớp bắt đầu từS[m] thất bại khi so sánh S[m + i] với W[i], thì vị trí của phép so khớp tiếp theo có chỉ số là m + i - T[i] trong S (T[i] 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 + i - T[i], giống như ví dụ ở trên, chúng ta không cần so sánh các kí tự T[i] sau nó, vì vậy chúng ta chỉ cần tiếp tục so sánh từ kí tự W[T[i]]. Ta có T[0] = -1, cho thấy rằng nếu W[0] 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 kmp_search:
    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,
            let m ← m + i - T[i],
            if T[i] lớn hơn -1,
                let i ← T[i]
            else
                let i ← 0
            
    return độ dài của đoạn văn bản S

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

Với sự xuất hiện của mảng T, phần tìm kiếm của thuật toán Knuth–Morris–Pratt có độ phức tạp O(k), trong đó k là độ dài của xâu S. 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 while, 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 T. Theo định nghĩa, mảng được tạo để: nếu một phép so khớp bắt đầu ở vị trí S[m] thất bại khi so sánh S[m + i] với W[i], thì phép so khớp có thể thành công tiếp theo sẽ bắt đầu ở vị trí S[m + (i - T[i])]. 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, vì vậyT[i] < i.

Từ điều này, chúng ta thấy rằng vòng lặp có thế thức hiện 2k 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 i và không thay đổi m, vì vậy chỉ số m + i của kí tự đang so sánh trên S tăng lên. Nhánh thứ hai cộng thêm i - T[i] vào m, và như chúng ta đã biết, đây luôn là số dương. Vì vậy, vị trí m, 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 m + i = k; vì vậy mỗi nhánh của vòng lặp có thể được sử dụng trong tối đa k lần, do chúng lần lượt tăng giá trị của m + i hoặc m, và m ≤ m + i: nếu m = k, thì m + i ≥ k, vì vậy: do các phép toán chủ yếu tăng theo đơn vị, chúng ta đã có m + i = k 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 2k lần, độ phức tạp tính toán của thuật toán tìm kiếm chỉ là O(k).

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

Mục đích của bảng là cho phép thuật toán so sánh mỗi kí tự của S 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ỏ quá 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 ra muốn tìm kiếm, với mỗi vị trí trên W, độ dài của đoạn dài nhất giống với “đoạn bắt đầu” trên W tính đến (không bao gồm) vị trí đó, đây là khoảng cách chúng ra có thể lùi lại để tiếp tục so khớp. Do vậy T[i] là giá trị của độ dài đoạn dài nhất kết thúc bởi phần tửW[i - 1]. 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 T[0] = -1.

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

Ta xét xâu W = "ABCDABD". 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ánT[0] = -1. Để tính T[1], ta cần tìm ra một xâu con "A" đồng thời cũng là xâu con bắt đầu của W. Vì vậy ta gán T[1] = 0. Tương tự , T[2] = 0 và T[3] = 0.

Ta xét đến kí tự W[4], 'A'. Dễ thấy kí tự này trùng với kí từ bắt đầu xâu W[0]. Nhưng do T[i] là độ dài xâu dài nhất trùng với xâu con bắt đầu trong W tính đến W[i – 1] nên T[4] = 0 và T[5] = 1. Tương tự, kí tự W[5] trùng với kí tự W[1]nên T[6] = 2.

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

i	0	1	2	3	4	5	6
W[i]	A	B	C	D	A	B	D
T[i]	-1	0	0	0	0	1	2

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

i	0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5	6	7	8	9	0	1	2	3
W[i]	P	A	R	T	I	C	I	P	A	T	E		I	N		P	A	R	A	C	H	U	T	E
T[i]	-1	0	0	0	0	0	0	0	1	2	0	0	0	0	0	0	1	2	3	0	0	0	0	0

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

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 kmp_table:
    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

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

Độ phức tạp của thuật toán tạo bảng là O(n), với n là độ dài của W. 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 while, độ phức tạp của toàn bộ vòng lặp là O(n), với việc cùng lúc sử lý giá trị của pos và pos - cnd. Trong trường hợp thứ nhất, pos - cnd không thay đổi, khi cả pos và cnd cùng tăng lên một đơn vị. Ở trường hợp hai, cnd được thay thế bởi T[cnd], như chúng ta đã biết ở trên, luôn luôn nhỏ hơn cnd, do đó tăng giá trị của pos - cnd. Trong trường hợp thứ ba, postăng và cnd thì không, nên cả giá trị của pos và pos - cnd đều tăng. Mà pos ≥ pos - cnd, điều này có nghĩa là ở mỗi bước hoặc pos hoặc chặn dưới pos đều tăng; mà thuật toán kết thúc khi pos = n, nên nó phải kết thúc tối đa sau 2n vòng lặp, do pos - cnd bắt đầu với giá trị 1. Vì vậy độ phức tạp của thuật toán xây dựng bảng là O(n).

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

Do độ phức tạp của hai phần trong thuật toán lần lượt là O(k) và O(n), nên độ phức tạp của cả thuật toán là O(n + k).

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 T bởi sự hiện diện của các số không. Một từ như"ABCDEFG" 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ừ W = "AAAAAAA" nó hoạt động tồi tệ, bởi vì bảng sẽ là

i	0	1	2	3	4	5	6
W[i]	A	A	A	A	A	A	A
T[i]	-1	0	1	2	3	4	5

Đây là mẫu xấu nhất cho mảng T, và nó có thể dùng để so sánh với đoạn như S = "AAAAAABAAAAAABAAAAAAA", trong trường hợp này thuật toán sẽ cố gắng ghép tất cả các chữ 'A' 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 "AAAAAAB" 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ữ W, 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ừ Wđược dùng để tìm trên xâu như xâu S, độ phức tạp tổng thể sẽ rất lớn. Bằng cách so sách, sự kết hợp này là trường hợp tốt nhất vớithuậ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.

[sửa]

Link: http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Knuth%E2%80%93Morris%E2%80%93Pratt

Một bài khác:

ICS 161: Design and Analysis of Algorithms
Lecture notes for February 27, 1996

---

Knuth-Morris-Pratt string matching

The problem: given a (short) pattern and a (long) text, both strings, determine whether the pattern appears somewhere in the text. Last time we saw how to do this with finite automata. This time we'll go through the Knuth-Morris-Pratt (KMP) algorithm, which can be thought of as an efficient way to build these automata. I also have some working C++ source code which might help you understand the algorithm better.First let's look at a naive solution.
suppose the text is in an array: char T[n]
and the pattern is in another array: char P[m].
One simple method is just to try each possible position the pattern could appear in the text.
Naive string matching:

    for (i=0; T[i] != '\0'; i++)
    {
    for (j=0; T[i+j] != '\0' && P[j] != '\0' && T[i+j]==P[j]; j++) ;
    if (P[j] == '\0') found a match
    }

There are two nested loops; the inner one takes O(m) iterations and the outer one takes O(n) iterations so the total time is the product, O(mn). This is slow; we'd like to speed it up.In practice this works pretty well -- not usually as bad as this O(mn) worst case analysis. This is because the inner loop usually finds a mismatch quickly and move on to the next position without going through all m steps. But this method still can take O(mn) for some inputs. In one bad example, all characters in T[] are "a"s, and P[] is all "a"'s except for one "b" at the end. Then it takes m comparisons each time to discover that you don't have a match, so mn overall.
Here's a more typical example. Each row represents an iteration of the outer loop, with each character in the row representing the result of a comparison (X if the comparison was unequal). Suppose we're looking for pattern "nano" in text "banananobano".

     0  1  2  3  4  5  6  7  8  9 10 11
      T: b  a  n  a  n  a  n  o  b  a  n  o

    i=0: X
    i=1:    X
    i=2:       n  a  n  X
    i=3:          X
    i=4:             n  a  n  o
    i=5:                X
    i=6:                   n  X
    i=7:                         X
    i=8:                            X
    i=9:                               n  X
    i=10:                                 X

Some of these comparisons are wasted work! For instance, after iteration i=2, we know from the comparisons we've done that T[3]="a", so there is no point comparing it to "n" in iteration i=3. And we also know that T[4]="n", so there is no point making the same comparison in iteration i=4.

Skipping outer iterations

The Knuth-Morris-Pratt idea is, in this sort of situation, after you've invested a lot of work making comparisons in the inner loop of the code, you know a lot about what's in the text. Specifically, if you've found a partial match of j characters starting at position i, you know what's in positions T[i]...T[i+j-1].You can use this knowledge to save work in two ways. First, you can skip some iterations for which no match is possible. Try overlapping the partial match you've found with the new match you want to find:

    i=2: n  a  n
    i=3:    n  a  n  o

Here the two placements of the pattern conflict with each other -- we know from the i=2 iteration that T[3] and T[4] are "a" and "n", so they can't be the "n" and "a" that the i=3 iteration is looking for. We can keep skipping positions until we find one that doesn't conflict:

    i=2: n  a  n
    i=4:       n  a  n  o

Here the two "n"'s coincide. Define the overlap of two strings x and y to be the longest word that's a suffix of x and a prefix of y. Here the overlap of "nan" and "nano" is just "n". (We don't allow the overlap to be all of x or y, so it's not "nan"). In general the value of i we want to skip to is the one corresponding to the largest overlap with the current partial match:String matching with skipped iterations:

    i=0;
    while (i<n)
    {
    for (j=0; T[i+j] != '\0' && P[j] != '\0' && T[i+j]==P[j]; j++) ;
    if (P[j] == '\0') found a match;
    i = i + max(1, j-overlap(P[0..j-1],P[0..m]));
    }

Skipping inner iterations

The other optimization that can be done is to skip some iterations in the inner loop. Let's look at the same example, in which we skipped from i=2 to i=4:

    i=2: n  a  n
    i=4:       n  a  n  o

In this example, the "n" that overlaps has already been tested by the i=2 iteration. There's no need to test it again in the i=4 iteration. In general, if we have a nontrivial overlap with the last partial match, we can avoid testing a number of characters equal to the length of the overlap.This change produces (a version of) the KMP algorithm:
KMP, version 1:

    i=0;
    o=0;
    while (i<n)
    {
    for (j=o; T[i+j] != '\0' && P[j] != '\0' && T[i+j]==P[j]; j++) ;
    if (P[j] == '\0') found a match;
    o = overlap(P[0..j-1],P[0..m]);
    i = i + max(1, j-o);
    }

The only remaining detail is how to compute the overlap function. This is a function only of j, and not of the characters in T[], so we can compute it once in apreprocessing stage before we get to this part of the algorithm. First let's see how fast this algorithm is.

KMP time analysis

We still have an outer loop and an inner loop, so it looks like the time might still be O(mn). But we can count it a different way to see that it's actually always less than that. The idea is that every time through the inner loop, we do one comparison T[i+j]==P[j]. We can count the total time of the algorithm by counting how many comparisons we perform.We split the comparisons into two groups: those that return true, and those that return false. If a comparison returns true, we've determined the value of T[i+j]. Then in future iterations, as long as there is a nontrivial overlap involving T[i+j], we'll skip past that overlap and not make a comparison with that position again. So each position of T[] is only involved in one true comparison, and there can be n such comparisons total. On the other hand, there is at most one false comparison per iteration of the outer loop, so there can also only be n of those. As a result we see that this part of the KMP algorithm makes at most 2n comparisons and takes time O(n).

KMP and finite automata

If we look just at what happens to j during the algorithm above, it's sort of like a finite automaton. At each step j is set either to j+1 (in the inner loop, after a match) or to the overlap o (after a mismatch). At each step the value of o is just a function of j and doesn't depend on other information like the characters in T[]. So we can draw something like an automaton, with arrows connecting values of j and labeled with matches and mismatches.
The difference between this and the automata we are used to is that it has only two arrows out of each circle, instead of one per character. But we can still simulate it just like any other automaton, by placing a marker on the start state (j=0) and moving it around the arrows. Whenever we get a matching character in T[] we move on to the next character of the text. But whenever we get a mismatch we look at the same character in the next step, except for the case of a mismatch in the state j=0.
So in this example (the same as the one above) the automaton goes through the sequence of states:

    j=0
            mismatch T[0] != "n"
    j=0
            mismatch T[1] != "n"
    j=0
            match T[2] == "n"
    j=1
            match T[3] == "a"
    j=2
            match T[4] == "n"
    j=3
            mismatch T[5] != "o"
    j=1
            match T[5] == "a"
    j=2
            match T[6] == "n"
    j=3
            match T[7] == "o"
    j=4
            found match
    j=0
            mismatch T[8] != "n"
    j=0
            mismatch T[9] != "n"
    j=0
            match T[10] == "n"
    j=1
            mismatch T[11] != "a"
    j=0
            mismatch T[11] != "n"

This is essentially the same sequence of comparisons done by the KMP pseudocode above. So this automaton provides an equivalent definition of the KMP algorithm.As one student pointed out in lecture, the one transition in this automaton that may not be clear is the one from j=4 to j=0. In general, there should be a transition from j=m to some smaller value of j, which should happen on any character (there are no more matches to test before making this transition). If we want to find all occurrences of the pattern, we should be able to find an occurrence even if it overlaps another one. So for instance if the pattern were "nana", we should find both occurrences of it in the text "nanana". So the transition from j=m should go to the next longest position that can match, which is simply j=overlap(pattern,pattern). In this case overlap("nano","nano") is empty (all suffixes of "nano" use the letter "o", and no prefix does) so we go to j=0.

Alternate version of KMP

The automaton above can be translated back into pseudo-code, looking a little different from the pseudo-code we saw before but performing the same comparisons.KMP, version 2:

    j = 0;
    for (i = 0; i < n; i++)
    for (;;) {      // loop until break
        if (T[i] == P[j]) { // matches?
        j++;        // yes, move on to next state
        if (j == m) {   // maybe that was the last state
            found a match;
            j = overlap[j];
        }
        break;
        } else if (j == 0) break;   // no match in state j=0, give up
        else j = overlap[j];    // try shorter partial match
    }

The code inside each iteration of the outer loop is essentially the same as the function match from the C++ implementation I've made available. One advantage of this version of the code is that it tests characters one by one, rather than performing random access in the T[] array, so (as in the implementation) it can be made to work for stream-based input rather than having to read the whole text into memory first.The overlap[j] array stores the values of overlap(pattern[0..j-1],pattern), which we still need to show how to compute.
Since this algorithm performs the same comparisons as the other version of KMP, it takes the same amount of time, O(n). One way of proving this bound directly is to note, first, that there is one true comparison (in which T[i]==P[j]) per iteration of the outer loop, since we break out of the inner loop when this happens. So there are n of these total. Each of these comparisons results in increasing j by one. Each iteration of the inner loop in which we don't break out of the loop results in executing the statement j=overlap[j], which decreases j. Since j can only decrease as many times as it's increased, the total number of times this happens is also O(n).

Computing the overlap function

Recall that we defined the overlap of two strings x and y to be the longest word that's a suffix of x and a prefix of y. The missing component of the KMP algorithm is a computation of this overlap function: we need to know overlap(P[0..j-1],P) for each value of j>0. Once we've computed these values we can store them in an array and look them up when we need them.To compute these overlap functions, we need to know for strings x and y not just the longest word that's a suffix of x and a prefix of y, but all such words. The key fact to notice here is that if w is a suffix of x and a prefix of y, and it's not the longest such word, then it's also a suffix of overlap(x,y). (This follows simply from the fact that it's a suffix of x that is shorter than overlap(x,y) itself.) So we can list all words that are suffixes of x and prefixes of y by the following loop:

    while (x != empty) {
    x = overlap(x,y);
    output x;
    }

Now let's make another definition: say that shorten(x) is the prefix of x with one fewer character. The next simple observation to make is that shorten(overlap(x,y)) is still a prefix of y, but is also a suffix of shorten(x).So we can find overlap(x,y) by adding one more character to some word that's a suffix of shorten(x) and a prefix of y. We can just find all such words using the loop above, and return the first one for which adding one more character produces a valid overlap:
Overlap computation:

    z = overlap(shorten(x),y)
    while (last char of x != y[length(z)])
    {
    if (z = empty) return overlap(x,y) = empty
    else z = overlap(z,y)
    }
    return overlap(x,y) = z

So this gives us a recursive algorithm for computing the overlap function in general. If we apply this algorithm for x=some prefix of the pattern, and y=the pattern itself, we see that all recursive calls have similar arguments. So if we store each value as we compute it, we can look it up instead of computing it again. (This simple idea of storing results instead of recomputing them is known as dynamic programming; we discussed it somewhat in the first lecture and will see it in more detailnext time.)So replacing x by P[0..j-1] and y by P[0..m-1] in the pseudocode above and replacing recursive calls by lookups of previously computed values gives us a routine for the problem we're trying to solve, of computing these particular overlap values. The following pseudocode is taken (with some names changed) from the initialization code of the C++ implementation I've made available. The value in overlap[0] is just a flag to make the rest of the loop simpler. The code inside the for loop is the part that computes each overlap value.
KMP overlap computation:

    overlap[0] = -1;
    for (int i = 0; pattern[i] != '\0'; i++) {
    overlap[i + 1] = overlap[i] + 1;
    while (overlap[i + 1] > 0 &&
           pattern[i] != pattern[overlap[i + 1] - 1])
        overlap[i + 1] = overlap[overlap[i + 1] - 1] + 1;
    }
    return overlap;

Let's finish by analyzing the time taken by this part of the KMP algorithm. The outer loop executes m times. Each iteration of the inner loop decreases the value of the formula overlap[i+1], and this formula's value only increases by one when we move from one iteration of the outer loop to the next. Since the number of decreases is at most the number of increases, the inner loop also has at most m iterations, and the total time for the algorithm is O(m).The entire KMP algorithm consists of this overlap computation followed by the main part of the algorithm in which we scan the text (using the overlap values to speed up the scan). The first part takes O(m) and the second part takes O(n) time, so the total time is O(m+n).

---

ICS 161 -- Dept. Information & Computer Science -- UC Irvine
Last update: 02 May 2000, 20:17:38 PDT

Link: http://www.ics.uci.edu/~eppstein/161/960227.html