模式搜尋演算法用於從另一個更大的字串中查詢模式或子字串。存在不同的演算法。設計此類演算法的主要目標是降低時間複雜度。對於較長的文字，傳統方法可能需要大量時間才能完成模式搜尋任務。在這裡，我們將看到不同的演算法以獲得更好的模式匹配效能。在本節中，我們將介紹以下內容：Aho-Corasick 演算法、字謎模式搜尋、壞字元啟發式、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 是模式的長度。輸入和 ... 閱讀更多