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