Thuật toán Knuth-Morris-Pratt trong tìm kiếm xâu con

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về thuật to&aacute;n Knuth-Morris-Pratt được &aacute;p dụng trong t&igrave;m kiếm chuỗi con trong một chuỗi kh&aacute;c. Ta sẽ lấy v&iacute; dụ minh họa cho thuật to&aacute;n n&agrave;y.</p> <h2 style="text-align: justify;">1. Tổng quan</h2> <p style="text-align: justify;">&Yacute; tưởng đằng sau c&aacute;ch tiếp cận đối s&aacute;nh mẫu n&agrave;y c&oacute; lẽ dễ nắm bắt nhất nếu ch&uacute;ng ta tưởng tượng việc đặt mẫu l&ecirc;n tr&ecirc;n văn bản v&agrave; trượt n&oacute; sang phải theo một c&aacute;ch nhất định.</p> <p style="text-align: justify;">Ta sẽ xem x&eacute;t v&iacute; dụ t&igrave;m kiếm mẫu abcabcacab trong chuỗi k&yacute; tự babcbabcabcaabcabcabcacabc. ban đầu ch&uacute;ng ta sẽ đặt mẫu ở phần b&ecirc;n tr&aacute;i v&agrave; chuẩn bị qu&eacute;t k&yacute; tự ngo&agrave;i c&ugrave;ng b&ecirc;n tr&aacute;i của văn bản đầu v&agrave;o.</p> <p><img style="width: 100%;" src="../../../public_files/69a85106-2569-4aea-a00f-9a942e010988" alt="thuat-toan-knuth-morris-pratt" /></p> <p style="text-align: justify;">Mũi t&ecirc;n ở đ&acirc;y cho biết k&yacute; tự văn bản hiện tại. V&igrave; n&oacute; trỏ đến b, kh&ocirc;ng khớp với a trong mẫu, do đ&oacute;, ch&uacute;ng ta sẽ chuyển mẫu dịch sang phải một khoảng v&agrave; chuyển sang vị tr&iacute; tiếp theo.</p> <p><img style="width: 100%;" src="../../../public_files/26815dd5-3779-4bb1-8ef1-dc5270f026a2" alt="thuat-toan-knuth-morris-pratt-2" /></p> <p style="text-align: justify;">B&acirc;y giờ ch&uacute;ng ta c&oacute; thể thấy c&oacute; một sự tr&ugrave;ng khớp ở đ&acirc;y, v&igrave; vậy mẫu vẫn được giữ nguy&ecirc;n trong khi c&aacute;c k&yacute; tự tiếp theo sẽ được qu&eacute;t.</p> <p><img style="width: 100%;" src="../../../public_files/c2793ce7-4b5e-49fe-807f-193464b69504" alt="thuat-toan-knuth-morris-pratt-3" /></p> <p style="text-align: justify;">V&agrave; theo c&aacute;ch tiếp c&acirc;n như vậy, ta sẽ cứ tiếp tục kiểm tra lần lượt từng k&yacute; tự trong mẫu so với chuỗi k&yacute; tự. Điều n&agrave;y sẽ g&acirc;y tồn nhiếu thời gian nếu chuỗi d&agrave;i hơn v&agrave; lớn hơn. Do đ&oacute;, thuật to&aacute;n Knuth-Morris-Pratt sẽ được ứng dụng để giải quyết b&agrave;i to&aacute;n n&agrave;y.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">2. Thuật to&aacute;n Knuth-Morris-Pratt</h2> <p style="text-align: justify;">Năm 1977, Donald Knuth, Vaughan Pratt v&agrave; James H. Morris đ&atilde; đưa ra một thuật to&aacute;n t&igrave;m kiếm chuỗi được gọi l&agrave; thuật to&aacute;n KMP. Trong thuật to&aacute;n KMP, ta sẽ cố gắng bỏ qua một số chữ c&aacute;i.</p> <p style="text-align: justify;">Thuật to&aacute;n hoạt động như sau:</p> <ul style="text-align: justify;"> <li>Đầu ti&ecirc;n, ch&uacute;ng ta cần tạo một bảng đối s&aacute;nh mẫu P.</li> <li>Sau đ&oacute;, ch&uacute;ng ta sẽ kiểm tra c&aacute;c mẫu bằng sự trợ gi&uacute;p của bảng P.</li> <li>Nếu bất kỳ k&yacute; tự n&agrave;o kh&ocirc;ng khớp, ch&uacute;ng ta c&oacute; thể bỏ qua một số k&yacute; tự dựa tr&ecirc;n bảng P n&agrave;y.</li> </ul> <h3 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">Bảng đối s&aacute;nh từng phần</h3> <p style="text-align: justify;">&Yacute; tưởng ch&iacute;nh của KMP ch&iacute;nh l&agrave; nằm ở bảng đối s&aacute;nh một phần. Sau đ&acirc;y l&agrave; bảng đối s&aacute;nh từng phần cho mẫu cần t&igrave;m kiếm&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae77d256646918" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-s">"abababca"</span></span></span>&nbsp;như sau:</p> <table style="border-collapse: collapse; width: 76.3623%; height: 66px; margin-left: auto; margin-right: auto;" border="1"> <tbody> <tr style="height: 22px;"> <td style="width: 10.1673%; text-align: center; height: 22px;" width="63">K&yacute; tự</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;a</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;b</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;a</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;b</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;a</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;b</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;c</td> <td style="width: 10.0273%; text-align: center; height: 22px;" width="62">&nbsp;a</td> </tr> <tr style="height: 22px;"> <td style="width: 10.1673%; text-align: center; height: 22px;" width="63">Chỉ số</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;0</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;1</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;2</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;3</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;4</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;5</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;6</td> <td style="width: 10.0273%; text-align: center; height: 22px;" width="62">&nbsp;7</td> </tr> <tr style="height: 22px;"> <td style="width: 10.1673%; text-align: center; height: 22px;" width="63">Gi&aacute; trị</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;0</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;0</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;1</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;2</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;3</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;4</td> <td style="width: 10.0233%; text-align: center; height: 22px;" width="62">&nbsp;0</td> <td style="width: 10.0273%; text-align: center; height: 22px;" width="62">&nbsp;1</td> </tr> </tbody> </table> <p style="text-align: justify;">Nếu ta c&oacute; một mẫu t&aacute;m k&yacute; tự (giả sử l&agrave; &ldquo;abababca&rdquo;), bảng đối s&aacute;nh từng phần của ta sẽ c&oacute; t&aacute;m &ocirc;. Nếu ta nh&igrave;n v&agrave;o &ocirc; thứ t&aacute;m v&agrave; &ocirc; cuối c&ugrave;ng trong bảng, ta sẽ quan t&acirc;m đến to&agrave;n bộ mẫu (&ldquo;abababca&rdquo;). Nếu ta nh&igrave;n v&agrave;o &ocirc; thứ bảy trong bảng, ta sẽ chỉ quan t&acirc;m đến bảy k&yacute; tự đầu ti&ecirc;n trong mẫu (&ldquo;abababc&rdquo;); chữ c&aacute;i thứ t&aacute;m (&ldquo;a&rdquo;) kh&ocirc;ng li&ecirc;n quan. Nếu ta nh&igrave;n v&agrave;o &ocirc; thứ s&aacute;u của bảng, th&igrave; ta sẽ chỉ quan t&acirc;m tới 6 chữ c&aacute;i đầu ti&ecirc;n, v&agrave; cứ như vậy. Lưu &yacute; rằng ta chưa c&oacute; n&oacute;i về &yacute; nghĩa của từng &ocirc; m&agrave; mới chỉ l&agrave; lướt qua.</p> <p style="text-align: justify;">B&acirc;y giờ, để n&oacute;i về &yacute; nghĩa, ch&uacute;ng ta cần biết về tiền tố th&iacute;ch hợp (Proper Prefixes) v&agrave; hậu tố th&iacute;ch hợp (Proper Suffixes).</p> <ul style="text-align: justify;"> <li>Tiền tố th&iacute;ch hợp: Tất cả c&aacute;c k&yacute; tự trong một chuỗi, với một hoặc nhiều k&yacute; tự bị cắt ở cuối. &ldquo;S&rdquo;, &ldquo;Sn&rdquo;, &ldquo;Sna&rdquo; v&agrave; &ldquo;Snak&rdquo; đều l&agrave; tiền tố th&iacute;ch hợp của &ldquo;Snake&rdquo;.</li> <li>Hậu tố th&iacute;ch hợp: Tất cả c&aacute;c k&yacute; tự trong một chuỗi, c&oacute; một hoặc nhiều k&yacute; tự bị cắt bỏ phần đầu. &ldquo;alo&rdquo;, &ldquo;uffalo&rdquo;, &ldquo;lo&rdquo;, &ldquo;o&rdquo; đều l&agrave; hậu tố th&iacute;ch hợp của &ldquo;Buffalo&rdquo;.</li> </ul> <p style="text-align: justify;">T&oacute;m lại, &yacute; tưởng ch&iacute;nh l&agrave;:</p> <p style="text-align: justify;"><strong>Độ d&agrave;i của tiền tố th&iacute;ch hợp d&agrave;i nhất trong mẫu (con) khớp với một hậu tố th&iacute;ch hợp trong c&ugrave;ng một mẫu (con).</strong></p> <p style="text-align: justify;">Ch&uacute;ng ta sẽ xem x&eacute;t về điều đ&oacute; như sau. Giả sử ch&uacute;ng ta đang t&igrave;m kiếm trong &ocirc; thứ ba. Như đ&atilde; đề cập ở tr&ecirc;n, điều n&agrave;y c&oacute; nghĩa l&agrave; ch&uacute;ng ta chỉ quan t&acirc;m đến ba k&yacute; tự đầu ti&ecirc;n (&ldquo;aba&rdquo;). Trong &ldquo;aba&rdquo;, c&oacute; hai tiền tố th&iacute;ch hợp l&agrave; &ldquo;a&rdquo; v&agrave; &ldquo;ab&rdquo; v&agrave; hai hậu tố th&iacute;ch hợp (&ldquo;a&rdquo; v&agrave; &ldquo;ba&rdquo;). Tiền tố th&iacute;ch hợp &ldquo;ab&rdquo; kh&ocirc;ng khớp với một trong hai hậu tố th&iacute;ch hợp. Tuy nhi&ecirc;n, tiền tố th&iacute;ch hợp &ldquo;a&rdquo; khớp với hậu tố th&iacute;ch hợp &ldquo;a&rdquo;. Do đ&oacute;, độ d&agrave;i của tiền tố th&iacute;ch hợp d&agrave;i nhất khớp với hậu tố th&iacute;ch hợp, trong trường hợp n&agrave;y, l&agrave; 1.</p> <p style="text-align: justify;">Ta sẽ thử n&oacute; cho &ocirc; số bốn. Ở đ&acirc;y, ch&uacute;ng ta quan t&acirc;m đến bốn k&yacute; tự đầu ti&ecirc;n (&ldquo;abab&rdquo;). Ch&uacute;ng ta c&oacute; ba tiền tố th&iacute;ch hợp l&agrave; &ldquo;a&rdquo;, &ldquo;ab&rdquo; v&agrave; &ldquo;aba&rdquo; v&agrave; ba hậu tố th&iacute;ch hợp (&ldquo;b&rdquo;, &ldquo;ab&rdquo; v&agrave; &ldquo;bab&rdquo;). Lần n&agrave;y, &ldquo;ab&rdquo; c&oacute; trong cả hậu tố v&agrave; tiền tố th&iacute;ch hợp v&agrave; c&oacute; độ d&agrave;i l&agrave; hai k&yacute; tự, v&igrave; vậy &ocirc; bốn nhận gi&aacute; trị 2.</p> <p style="text-align: justify;">Ch&uacute;ng ta sẽ cũng thử n&oacute; cho &ocirc; số năm l&agrave; &ldquo;ababa&rdquo;. Ch&uacute;ng ta c&oacute; bốn tiền tố th&iacute;ch hợp (&ldquo;a&rdquo;, &ldquo;ab&rdquo;, &ldquo;aba&rdquo; v&agrave; &ldquo;abab&rdquo;) v&agrave; bốn hậu tố th&iacute;ch hợp (&ldquo;a&rdquo;, &ldquo;ba&rdquo;, &ldquo;aba&rdquo; v&agrave; &ldquo;baba&rdquo;). B&acirc;y giờ, ch&uacute;ng ta c&oacute; hai kết quả ph&ugrave; hợp l&agrave; &ldquo;a&rdquo; v&agrave; &ldquo;aba&rdquo; đều l&agrave; tiền tố th&iacute;ch hợp v&agrave; hậu tố th&iacute;ch hợp. V&igrave; &ldquo;aba&rdquo; d&agrave;i hơn &ldquo;a&rdquo; n&ecirc;n n&oacute; sẽ được chọn v&agrave; &ocirc; năm nhận gi&aacute; trị 3.</p> <p style="text-align: justify;">Giờ ta sẽ chuyển sang &ocirc; thứ bảy (&ocirc; thứ hai đến &ocirc; cuối c&ugrave;ng), c&oacute; li&ecirc;n quan đến mẫu &ldquo;abababc&rdquo;. Ngay cả khi kh&ocirc;ng liệt k&ecirc; tất cả c&aacute;c tiền tố v&agrave; hậu tố th&iacute;ch hợp, r&otilde; r&agrave;ng l&agrave; sẽ kh&ocirc;ng c&oacute; bất kỳ kết quả ph&ugrave; hợp n&agrave;o; tất cả c&aacute;c hậu tố sẽ kết th&uacute;c bằng chữ c&aacute;i &ldquo;c&rdquo; v&agrave; kh&ocirc;ng c&oacute; tiền tố n&agrave;o kh&aacute;c. V&igrave; kh&ocirc;ng c&oacute; kết quả ph&ugrave; hợp n&agrave;o n&ecirc;n &ocirc; thứ bảy nhận gi&aacute; trị l&agrave; 0.</p> <p style="text-align: justify;">Cuối c&ugrave;ng, ta sẽ xem x&eacute;t &ocirc; số t&aacute;m, &ocirc; n&agrave;y li&ecirc;n quan đến to&agrave;n bộ mẫu (&ldquo;abababca&rdquo;). V&igrave; cả hai đều bắt đầu v&agrave; kết th&uacute;c bằng &ldquo;a&rdquo;, ch&uacute;ng ta biết rằng chắc chắn sẽ c&oacute; gi&aacute; trị &iacute;t nhất l&agrave; 1. Từ độ d&agrave;i từ hai trở l&ecirc;n, tất cả c&aacute;c hậu tố đều chứa c, trong khi chỉ c&oacute; tiền tố cuối c&ugrave;ng (&ldquo;abababc&rdquo;). Tiền tố bảy k&yacute; tự n&agrave;y kh&ocirc;ng khớp với hậu tố bảy k&yacute; tự (&ldquo;bababca&rdquo;), v&igrave; vậy &ocirc; t&aacute;m nhận gi&aacute; trị l&agrave; 1.</p> <h3 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">L&agrave;m c&aacute;ch n&agrave;o để sử dụng bảng đối s&aacute;nh một phần?</h3> <p style="text-align: justify;">Ch&uacute;ng ta c&oacute; thể sử dụng c&aacute;c gi&aacute; trị trong bảng đối s&aacute;nh từng phần để bỏ qua (thay v&igrave; thực hiện lại c&aacute;c so s&aacute;nh cũ kh&ocirc;ng cần thiết) khi ch&uacute;ng ta t&igrave;m thấy đối s&aacute;nh từng phần. C&ocirc;ng thức hoạt động như sau:</p> <p style="text-align: left;">Nếu t&igrave;m thấy kết quả tr&ugrave;ng khớp một phần của độ d&agrave;i&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae78f823656933" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">part_match_length</span></span></span>&nbsp;v&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae79e171887084" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-v">part_match_length</span><span class="crayon-sy">]</span><span class="crayon-o">&gt;</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span></span></span>, ch&uacute;ng ta c&oacute; thể bỏ qua <span id="urvanov-syntax-highlighter-6108a429ae7a1473879932" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">part_match_length </span><span class="crayon-o">- </span><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-v">part_match_length </span><span class="crayon-o">- </span><span class="crayon-cn">1</span><span class="crayon-sy">] </span></span></span>k&yacute; tự.</p> <p style="text-align: justify;">Giả sử ch&uacute;ng ta đang đối s&aacute;nh mẫu &ldquo;abababca&rdquo; với một đoạn văn bản &ldquo;bacbababaabcbab&rdquo;. Sau đ&acirc;y l&agrave; bảng đối s&aacute;nh từng phần của ch&uacute;ng ta để dễ d&agrave;ng tham chiếu:</p> <table style="border-collapse: collapse; width: 53.7694%; height: 128px; margin-left: auto; margin-right: auto;" border="1"> <tbody> <tr> <td style="width: 10.0396%; text-align: center;" width="62">K&yacute; tự</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;a</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;b</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;a</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;b</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;a</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;b</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;c</td> <td style="width: 10.049%; text-align: center;" width="62">&nbsp;a</td> </tr> <tr> <td style="width: 10.0396%; text-align: center;" width="62">Chỉ số</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;0</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;1</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;2</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;3</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;4</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;5</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;6</td> <td style="width: 10.049%; text-align: center;" width="62">&nbsp;7</td> </tr> <tr> <td style="width: 10.0396%; text-align: center;" width="62">Gi&aacute; trị</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;0</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;0</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;1</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;2</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;3</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;4</td> <td style="width: 10.0396%; text-align: center;" width="62">&nbsp;0</td> <td style="width: 10.049%; text-align: center;" width="62">&nbsp;1</td> </tr> </tbody> </table> <p>Đầu ti&ecirc;n ch&uacute;ng ta c&oacute; được sự tr&ugrave;ng khợp một phần nằm tại vị tr&iacute; như trong h&igrave;nh dưới đ&acirc;y:</p> <p><img style="width: 100%;" src="../../../public_files/d485814c-247e-40dc-ac14-63f16eb9dc1c" alt="thuat-toan-knuth-morris-pratt-4" /></p> <p style="text-align: justify;">Độ d&agrave;i của đối s&aacute;nh một phần&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7a7651234526" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">partial_match_length</span></span></span>&nbsp;trong trường hợp n&agrave;y l&agrave; 1. Gi&aacute; trị tại&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7aa136297465" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-v">part_match_length</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span></span></span>&nbsp;(hoặc&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7ac474060578" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-cn">0</span><span class="crayon-sy">]</span></span></span>) l&agrave; 0, v&igrave; vậy ch&uacute;ng ta sẽ kh&ocirc;ng thể bỏ qua bất kỳ k&yacute; tự n&agrave;o. Đối s&aacute;nh một phần tiếp theo m&agrave; ch&uacute;ng ta nhận được l&agrave;:</p> <p><img style="width: 100%;" src="../../../public_files/ab1f174c-f4ad-4368-a3f2-5ed19e41b325" alt="thuat-toan-knuth-morris-pratt-5" /></p> <p style="text-align: justify;">Độ d&agrave;i đối s&aacute;nh một phần trong trường hợp n&agrave;y l&agrave; 5. Gi&aacute; trị tại&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7af874144597" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-v">part_match_length</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span></span></span>&nbsp;(hoặc&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7b5575990000" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-cn">4</span><span class="crayon-sy">]</span></span></span>) l&agrave; 3. Điều n&agrave;y c&oacute; nghĩa l&agrave; ta sẽ bỏ qua&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7b8401050544" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">partial_match_length</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-v">partial_match_length</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span></span></span>&nbsp;hay&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7bb840617360" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-cn">5</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-cn">4</span><span class="crayon-sy">]</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">5</span><span class="crayon-h">&nbsp;</span>&ndash;<span class="crayon-h">&nbsp;</span><span class="crayon-cn">3</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">2</span></span></span>&nbsp;k&yacute; tự.</p> <p><img style="width: 100%;" src="../../../public_files/199b01f3-753e-42ee-a5dd-e375d29b9344" alt="thuat-toan-knuth-morris-pratt-6" /></p> <p style="text-align: justify;">Trong đ&oacute; x l&agrave; k&yacute; tự bỏ qua.</p> <p style="text-align: justify;">Độ d&agrave;i của đối s&aacute;nh một phần trong trường hợp n&agrave;y l&agrave; 3. Gi&aacute; trị tại&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7be236637103" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-v">part_match_length</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span></span></span>&nbsp;(hoặc&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7c0704761068" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-cn">2</span><span class="crayon-sy">]</span></span></span>) l&agrave; 1. Điều đ&oacute; c&oacute; nghĩa l&agrave; ch&uacute;ng ta c&oacute; thể bỏ qua&nbsp;<span id="urvanov-syntax-highlighter-6108a429ae7c3734585595" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">partial_match_length</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-v">partial_match_length</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">3</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">table</span><span class="crayon-sy">[</span><span class="crayon-cn">2</span><span class="crayon-sy">]</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">3</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">2</span></span></span>&nbsp;k&yacute; tự.</p> <p><img style="width: 100%;" src="../../../public_files/1492139a-458d-480b-b556-33cd1c69b1f3" alt="thuat-toan-knuth-morris-pratt-7" /></p> <p style="text-align: justify;">Tại đ&acirc;y, mẫu của ch&uacute;ng ta d&agrave;i hơn c&aacute;c k&yacute; tự c&ograve;n lại trong văn bản, v&igrave; vậy ch&uacute;ng ta biết rằng sẽ kh&ocirc;ng c&oacute; sự tr&ugrave;ng khớp n&agrave;o.</p> <p style="text-align: justify;">Như vậy, ta đ&atilde; ho&agrave;n th&agrave;nh xong thuật to&aacute;n Knuth-Morris-Pratt.</p> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">3. Độ phức tạp của thuật to&aacute;n Knuth-Morris-Pratt</h2> <p style="text-align: justify;">Đối với t&iacute;nh to&aacute;n bảng P, v&ograve;ng lặp for được lặp lại $m - 1$ lần trong đ&oacute; m l&agrave; k&iacute;ch thước của chuỗi mẫu. Độ phức tạp của phần đ&oacute; l&agrave; $O(m)$. V&agrave; trong phần đối s&aacute;nh KMP, v&ograve;ng lặp chạy n lần trong đ&oacute; n l&agrave; k&iacute;ch thước của văn bản S. V&igrave; vậy, độ phức tạp về thời gian cho phần đối s&aacute;nh l&agrave; $O(n)$. V&agrave; thuật to&aacute;n KMP chạy ở độ phức tạp về thời gian l&agrave; $O(m + n)$. Độ phức tạp về kh&ocirc;ng gian của thuật to&aacute;n n&agrave;y l&agrave; $O(n)$.</p> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về danh s&aacute;ch li&ecirc;n kết đ&ocirc;i. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>