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

從給定的字串中，我們可以獲得所有可能的字尾。按字典序對字尾排序後，我們可以得到字尾陣列。字尾陣列也可以使用字尾樹來構建。使用字尾樹的深度優先搜尋遍歷，我們可以得到字尾陣列。字尾陣列有助於線上性時間內查詢字尾。我們還可以使用類似二分查詢的方法，使用字尾陣列查詢子串。時間複雜度為 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 是模式的長度。輸入和… 閱讀更多

迴文基本上是給定字串或模式的所有排列。這種模式搜尋演算法略有不同。在這種情況下，不僅搜尋確切的模式，還搜尋文字中給定模式的所有可能排列。為了解決這個問題，我們將整個文字劃分為幾個長度與模式相同的視窗。然後計算並存儲模式中每個字元的計數。對於每個視窗，我們還嘗試查詢計數陣列，然後檢查它們是否匹配。迴文模式搜尋演算法的時間複雜度為 O(n)。輸入… 閱讀更多

該演算法有助於查詢所有給定關鍵詞的所有出現位置。這是一種字典匹配演算法。它使用包含所有關鍵詞的樹結構。構建樹之後，它嘗試將樹轉換為自動機，以便線性時間內進行搜尋。Aho-Corasick演算法共有三個階段：跳轉(Go-to)、失敗(Failure)和輸出(Output)。在跳轉階段，它使用所有關鍵詞構建樹。在下一個階段，即失敗階段，它嘗試查詢向後轉換以獲得某些關鍵詞的適當字尾。在……閱讀更多