模式搜尋演算法用於在一個較大的字串中查詢模式或子字串。存在不同的演算法。設計這類演算法的主要目標是降低時間複雜度。對於較長的文字，傳統方法可能需要很長時間才能完成模式搜尋任務。在這裡，我們將看到不同的演算法，以獲得更好的模式匹配效能。在本節中，我們將介紹：Aho-Corasick演算法、Anagram模式搜尋、壞字元啟發式演算法、Boyer Moore演算法、有限自動機的有效構造、Kasai演算法、Knuth-Morris-Pratt演算法、Manacher演算法、樸素模式搜尋、Rabin-Karp演算法…… 閱讀更多

該演算法名為Z演算法，因為在這個演算法中，我們需要建立一個Z陣列。Z陣列的大小與文字大小相同。該陣列用於儲存從主字串當前字元開始的最長可能子字串的長度。首先，模式和主文字用文字和模式中不存在的特殊符號連線起來。如果P是模式，T是主文字，那麼連線後將是P$T（假設$不在P中）…… 閱讀更多

我們可以從文字中生成所有後綴以建立樹結構。我們知道，文字中出現的每個模式都必須是文字中某個可能字尾的字首。透過構建所有後綴的Trie樹，我們可以線性時間內找到任何子字串。每個字尾都以字串終止符結尾。如果從每個節點存在任何路徑，它將向前移動，否則返回未找到該模式。對於此演算法，時間複雜度為O(m+k)，其中m是字串的長度，k是模式的頻率…… 閱讀更多

從給定的字串中，我們可以得到所有可能的字尾。按照字典順序對字尾進行排序後，我們可以得到字尾陣列。字尾陣列也可以使用字尾樹來形成。使用字尾樹的DFS遍歷，我們可以得到字尾陣列。字尾陣列有助於線性時間內查詢字尾。我們還可以使用類似二分查詢的過程，使用字尾陣列查詢子字串。時間複雜度為O(m log n) 輸入和輸出 輸入：主字串：“BANANA”，模式：“NAN” 輸出：模式在位置2處找到演算法 fillSuffixArray (text, suffArray) 輸入：主字串 輸出：字尾陣列 開始 n := text Length … 閱讀更多

Rabin-Karp是另一種模式搜尋演算法，可以更有效地查詢模式。它也逐個移動視窗來檢查模式，但是它不會檢查所有情況下的所有字元，而是查詢雜湊值。只有當雜湊值匹配時，它才會嘗試檢查每個字元。此過程使演算法更有效。時間複雜度為O(m+n)，但對於最壞情況，它為O(mn)。輸入和輸出 輸入：主字串：“ABAAABCDBBABCDDEBCABC”，模式“ABC” 輸出：模式在位置4、10和18處找到 演算法 rabinKarpSearch(text, pattern, prime) 輸入 - 主… 閱讀更多

樸素模式搜尋是在其他模式搜尋演算法中最簡單的方法。它檢查主字串的所有字元與模式是否匹配。此演算法適用於較小的文字。它不需要任何預處理階段。我們可以透過一次檢查字串來查詢子字串。它也不佔用額外的空間來執行操作。樸素模式搜尋方法的時間複雜度為O(m*n)。m是模式的大小，n是主字串的大小。輸入和輸出 輸入：主字串：“ABAAABCDBBABCDDEBCABC”，模式：“ABC” 輸出：模式在位置4處找到… 閱讀更多

為了從字串中找到最長的迴文子串，我們可以使用Manacher演算法。透過選擇每個字元，我們將嘗試使用左右指標查詢是否存在任何迴文。還有一個數組用於儲存資訊，我們可以很容易地從中找到迴文有多長。對於每個字元，陣列將儲存資訊。遍歷整個字串後，我們可以從建立的陣列中找到最長的迴文子序列。該演算法的時間複雜度為O(n)。輸入和輸出 輸入：字串：“levelup” 輸出：最長迴文是：level 演算法 longestPalindrome(text) 輸入 - 用於查詢最長迴文的文字 輸出 - … 閱讀更多

Kasai演算法用於從字尾陣列中獲取最長公共字首（LCP）陣列。首先找到字尾陣列。之後，Kasai演算法獲取字尾陣列列表以查詢LCP。對於LCP陣列，它需要O(m log n)，其中m是模式長度，n是文字的長度。Kasai演算法在主字串中搜索模式需要O(n)。輸入和輸出 輸入：主字串：“banana” 輸出：字尾陣列：5 3 1 0 4 2 公共字首陣列：1 3 0 0 2 0 演算法 buildSuffixArray(text) 輸入：主字串 輸出：構建的字尾陣列… 閱讀更多

透過構造有限自動機，我們可以簡單地在文字中執行模式搜尋。首先，我們必須填充一個二維陣列以建立有限自動機的轉移表。一旦建立了表，搜尋過程就很簡單了。從自動機的第一個狀態開始，當我們到達最終狀態時，這意味著在字串中找到了模式。對於有限自動機的構造，時間複雜度為O(M*K)，M是模式長度，K是不同字元的數量。主模式搜尋的複雜度為O(n)。輸入和輸出 輸入：主字串：… 閱讀更多

壞字元啟發式方法是Boyer Moore演算法的一種方法。另一種方法是好字尾啟發式方法。在這種方法中，我們將嘗試找到一個壞字元，即主字串中與模式不匹配的字元。當發生不匹配時，我們將移動整個模式，直到不匹配變成匹配，否則，模式將移動到壞字元之後。這裡，最佳情況下的時間複雜度為O(m/n)，最壞情況下的時間複雜度為O(mn)，其中n是文字長度，m是模式長度。輸入和……閱讀更多