在C 的程式設計中，字串比對問題是十分常見的問題。簡單來說，字串比對問題就是在文字字串中尋找特定的模式串的過程。在實際的應用中，字串匹配演算法主要用於文字搜尋、圖像辨識和自然語言處理等領域。本篇文章將著重介紹C 中常用的字串比對演算法及其實作。
樸素字串比對演算法也稱為暴力搜尋比對演算法。其想法就是透過對文字串T的每個位置都依序嘗試匹配模式串P，直到找到匹配的位置或是整個T中不存在P為止。此演算法的時間複雜度較高，為O(n*m)，n和m分別是文字串T和模式串P的長度。
C 程式碼實作如下：
void naive_match(string T, string P) { int n = T.length(); int m = P.length(); for(int i = 0; i <= n-m; i++) { int j; for(j = 0; j < m; j++) { if(T[i+j] != P[j]) break; } if(j == m) { cout << "Pattern occurs with shift " << i << endl; } } }
KMP字串比對演算法是一種經典的字串比對演算法，它的核心思想是透過對模式串P的前綴後綴的最長公共前綴後綴進行匹配，來避免在文本串T中對已經匹配過的字符進行重複匹配的過程。此演算法的時間複雜度為O(n)，n為文字串的長度。
C 程式碼實作如下：
void get_next(string P, vector& next) { int m = P.length(); next[0] = -1; int i = 0; int j = -1; while(i < m) { if(j == -1 || P[i] == P[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } } void kmp_match(string T, string P) { int n = T.length(); int m = P.length(); vector next(m+1); get_next(P, next); int i = 0; int j = 0; while(i < n) { if(j == -1 || T[i] == P[j]) { i++; j++; } else { j = next[j]; } if(j == m) { cout << "Pattern occurs with shift " << i-m << endl; j = next[j]; } } }
BM演算法是一種基於壞字元和好後綴規則的字串匹配演算法。它的核心思想是透過對模式串P的最後一個字元進行匹配，並透過對文字串T中不匹配的字元進行預處理，來跳過已經匹配過的字元。此演算法的時間複雜度為O(n)。
C 程式碼實作如下：
const int MAXCHAR = 256; void bm_match(string T, string P) { int n = T.length(); int m = P.length(); vector badchar(MAXCHAR, -1); for(int i = 0; i < m; i++) { badchar[int(P[i])] = i; } vector suffix(m+1); vector prefix(m+1); get_suffix_prefix(P, suffix, prefix); int i = 0; while(i <= n-m) { int j = m-1; while(j >= 0 && P[j] == T[i+j]) j--; if(j < 0) { cout << "Pattern occurs with shift " << i << endl; i += (i+m < n) ? m-badchar[int(T[i+m])] : 1; } else { i += max(suffix[j+1], j-badchar[int(T[i+j])]); } } }
本篇文章主要介紹了C 中常用的字串比對演算法及其實作。樸素字串匹配演算法雖然簡單，但時間複雜度較高，KMP和BM演算法則能夠更快速地找到匹配位置。其中，KMP演算法適用於模式串較短，BM演算法則適用於模式串較長的情況。在實際的應用中，我們需要根據不同的情況來選擇合適的演算法來進行字串匹配。
以上是C++中的字串比對演算法及其實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
