Sự phức tạp của trường hợp xấu nhất đối với KMP khi mục tiêu là tìm tất cả các lần xuất hiện của một chuỗi nhất định?

Question

Tôi cũng muốn biết thuật toán nào có trường hợp phức tạp nhất của tất cả để tìm tất cả các lần xuất hiện của chuỗi trong chuỗi khác. Có vẻ như thuật toán của Boyer – Moore có độ phức tạp về thời gian tuyến tính.

Answer 1

Thuật toán KMP có độ phức tạp tuyến tính để tìm tất cả các lần xuất hiện của một mẫu trong một chuỗi, như thuật toán Boyer-Moore¹. Nếu bạn cố gắng tìm ra một mô hình như "aaaaaa" trong một chuỗi như "aaaaaaaaa", một khi bạn có phù hợp với hoàn chỉnh đầu tiên,

aaaaaaaaa 
aaaaaa 
aaaaaa 
    ^

các table border chứa các thông tin mà các trận đấu tiếp theo dài nhất có thể (tương ứng với biên giới rộng nhất của mẫu) của một tiền tố của mẫu chỉ là một ký tự ngắn (một kết hợp hoàn chỉnh tương đương với một mẫu không phù hợp trong quá trình kết thúc mẫu theo khía cạnh này). Do đó, mẫu được di chuyển thêm một chỗ nữa và từ bảng biên giới, tất cả các ký tự của mẫu ngoại trừ kết quả cuối cùng, so sánh tiếp theo là giữa ký tự mẫu cuối cùng và ký tự văn bản được căn chỉnh. Trong trường hợp cụ thể này (tìm các lần xuất hiện của một ^m trong một ⁿ), đây là trường hợp xấu nhất cho thuật toán đối sánh ngây thơ, thuật toán KMP so sánh từng ký tự chính xác một lần.

Trong mỗi bước, ít nhất một trong

• vị trí của các nhân vật văn bản so
• vị trí của ký tự đầu tiên của mô hình liên quan đến văn bản

tăng, và không bao giờ giảm. Vị trí của ký tự văn bản được so sánh có thể tăng nhiều nhất là length(text)-1 lần, vị trí của ký tự mẫu đầu tiên có thể tăng tối đa length(text) - length(pattern) lần, do đó, thuật toán mất tối đa 2*length(text) - length(pattern) - 1 bước.

Các tiền xử lý (xây dựng các table border) mất ít nhất 2*length(pattern) bước, do đó tổng thể mức độ phức tạp là O (m + n) và không nhiều m + 2*n bước được thực hiện nếu m là chiều dài của mô hình và n chiều dài của văn bản.

¹ Lưu ý rằng các thuật toán Boyer-Moore như thường được trình bày có độ phức tạp trường hợp xấu nhất của O (m * n) cho mô hình định kỳ và các văn bản như một ^m và ⁿ nếu tất cả các trận đấu được yêu cầu, bởi vì sau khi kết hợp hoàn toàn,

aaaaaaaaa 
aaaaaa 
aaaaaa 
    ^
    <- <- 
^ 

toàn bộ mẫu sẽ được so sánh lại. Để tránh điều đó, bạn cần phải nhớ tiền tố của mẫu vẫn dài bao lâu sau khi thay đổi theo sau một kết hợp hoàn chỉnh và chỉ so sánh các ký tự mới.

Answer 2

Bạn có thể đếm hàm Pi cho một chuỗi trong O(length). KMP xây dựng một chuỗi đặc biệt mà có chiều dài n+m+1, và đếm chức năng Pi vào nó, vì vậy trong bất kỳ trường hợp phức tạp sẽ O(n+m+1)=O(n+m)

Answer 3

Có một bài viết dài trên KMP tại http://en.wikipedia.org/wiki/Knuth-morris-pratt kết thúc với câu nói

Kể từ khi hai phần của thuật toán, tương ứng, phức tạp của O (k) và O (n), độ phức tạp của thuật toán tổng thể là O (n + k).

Những phức tạp là như nhau, dù có bao nhiêu mẫu lặp đi lặp lại là trong W hoặc S. (end quote)

Vì vậy, tổng chi phí của một tìm kiếm KMP là tuyến tính trong số ký tự của chuỗi và mẫu . Tôi nghĩ rằng điều này giữ ngay cả khi bạn cần tìm nhiều lần xuất hiện của mẫu trong chuỗi - và nếu không, chỉ cần xem xét tìm kiếm patternQ, trong đó Q là ký tự không xuất hiện trong văn bản và ghi lại vị trí của trạng thái KMP rằng nó đã kết hợp mọi thứ lên đến Q.