第四章 串

一些面試題

12. 介紹一下KMP算法。★★★

? ? ? ?KMP算法是一種高效的字符串匹配算法，用于在一個文本串中查找一個模式串的出現位置。KMP算法通過利用模式串自身的信息，在匹配過程中避免不必要的回溯，從而提高匹配效率。

? ? ? ?KMP算法的核心思想是使用一個部分匹配表，也稱為next數組，來記錄模式串中每個位置的最長公共前后綴的長度。這樣，在匹配失敗時，可以根據部分匹配表的信息，將模式串向右移動盡可能少的步數。

? ? ? ?KMP算法的時間復雜度O(n+m)，樸素算法的時間復雜度O(n*m)，n和m是兩個串的長度。

-------------------------------------------------------------------------------------------------------------------------

? ? ? ?KMP算法的具體步驟如下：

預處理next數組：對于模式串，遍歷每個位置，計算該位置之前子串的最長公共前后綴的長度，并保存到next數組中。
匹配過程：從文本串的起始位置開始，用兩個指針分別指向文本串和模式串的當前位置，逐個字符進行比較。
? ? ? ?如果當前字符匹配成功，則兩個指針同時向后移動一位。

? ? ? ?如果當前字符匹配失敗：

? ? ? ?根據next數組中的信息，將模式串向右移動盡可能少的步數。根據當前失敗位置的部分匹配值，向右移動模式串的指針。

? ? ? ?同時，保持文本串的指針不動，繼續與模式串的新位置進行比較。

? ? ? ?如果模式串的指針移到末尾，則表示匹配成功，返回在文本串中的起始位置。如果文本串的指針移到末尾，則表示未找到匹配，返回-1。

--------------------------------------------------------------------------------------------------------------------------

KMP算法簡述

KMP算法是在簡單模式匹配的基礎上對串的模式匹配進行優化。

主要的思路是每趟比較過程中讓子串先滑動到一個合適的位置。

當發生不匹配時，不同于簡單模式匹配的右移一位，而是移動到適合的位置。

這里所移動的位置依靠與NEXT[]數組，求next[]數組的方法是比較前后綴相同元素。

計算機保研/考研面試題——數據結構與算法篇_計算機保研面試 csdn-CSDN博客

面試考點——數據結構篇_數據結構保研面試重點-CSDN博客