Nhiều bài viết về KMP đề cập đến chức năng lỗi trong bản thân KMP có một số lượng lớn các ứng dụng.Ứng dụng của chức năng lỗi KMP
Một ứng dụng như vậy là tìm chuỗi nhỏ nhất mà khi thời gian nối k cho chuỗi gốc (dấu chấm).
Nhưng tôi không thể tìm thấy bất kỳ mục đích nào khác. Các vấn đề khác liên quan đến chức năng thất bại KMP là gì?
KMP tính đường viền của tất cả các tiền tố của chuỗi, mà chính chúng là khái niệm then chốt trong thuật toán trên chuỗi. (Computing biên giới của toàn bộ từ chính nó là không tầm thường, và KMP (chức năng thất bại) là tiêu chuẩn để làm điều đó!)
Một biên giới s chỉ đơn giản là bất kỳ từ nào là cả một tiền tố và hậu tố của s.
Như bạn một cách đúng đắn để ý, một ứng dụng nổi bật về khả năng tính toán biên giới là khả năng tính toán chuỗi nhỏ w như vậy đối với một số k tự nhiên w^k = s cho một chuỗi cho trước s. Đây được gọi là gốc nguyên thủy trong số s.
Lý do cho điều này là tính hai mặt giữa các đường viền và các khoảng thời gian của một chuỗi. Một thời gian của một chuỗi s là bất kỳ chuỗi w không quá s mà s là tiền tố của chuỗi wwww ... Ví dụ, abc là một khoảng thời gian của abcabcab. Nó chỉ ra rằng có một sự tương ứng 1: 1 giữa các biên giới và các giai đoạn của một từ; trong ví dụ trên, hãy lưu ý rằng abcab là một đường viền của abcabcab. Nói chung, bất cứ khi nào w là một khoảng thời gian s, sau đó chuỗi những gì còn lại từ s sau khi gỡ bỏ w từ đầu của nó (w^-1 s) là một biên giới s . Tương tự, nếu w là một biên giới s, sau đó từ những gì còn lại từ s khi bạn loại bỏ các hậu tố w là một khoảng thời gian s.
Thời gian là công cụ quan trọng trong việc phân tích các thuộc tính của chuỗi. Chúng được sử dụng ví dụ trong các thuật toán để tìm sự lặp lại (chạy) trong chuỗi; để biết tổng quan, hãy xem this paper.