7-1 字符串匹配算法比较pta

### 字符串匹配算法性能比较 字符串匹配问题是计算机科学中的经典问题之一，在实际应用中有着广泛的应用场景。对于不同的应用场景，选择合适的字符串匹配算法至关重要。 #### 朴素模式匹配算法（Brute Force） 最简单的字符串匹配方法是逐个字符对比目标串 `T` 和模式串 `P` 中的每一个位置。这种方法的时间复杂度为 O(mn)，其中 m 是模式串长度而 n 是文本串长度。尽管实现简单，但在处理大规模数据时效率较低[^1]。 ```python def brute_force_match(text, pattern): n = len(text) m = len(pattern) for i in range(n - m + 1): j = 0 while(j < m and text[i+j] == pattern[j]): j += 1 if j == m: return True return False ``` #### KMP 算法 (Knuth-Morris-Pratt Algorithm) KMP 算法通过预计算部分匹配表来避免不必要的重复扫描操作，从而提高查找速度。其时间复杂度可以达到线性的O(n+m)[^2]。此算法特别适用于当模式串较长且存在大量相同前缀的情况。 ```python def compute_lps_array(pattern): lps = [0]*len(pattern) length = 0 i = 1 while i < len(pattern): if pattern[i]==pattern[length]: length+=1 lps[i]=length i+=1 else: if length!=0: length=lps[length-1] else: lps[i]=0 i+=1 return lps def kmp_search(text, pattern): lps = compute_lps_array(pattern) i = 0 # index for txt[] j = 0 # index for pat[] while ((n-i)>=(m-j)): if pattern[j] == text[i]: i += 1 j += 1 if j==m: return True j = lps[j-1] elif i<n and pattern[j]!=text[i]: if j != 0: j = lps[j-1] else: i += 1 return False ``` #### Boyer-Moore 算法 Boyer-Moore 算法则采取了另一种策略——尽可能多地跳过不可能成为解的位置来进行快速定位。它利用坏字符规则和好后缀规则两种机制实现了平均情况下优于其他传统算法的表现，尤其适合于短小精悍但频繁出现的目标子串搜索任务[^3]。 ```c++ void bm_preprocess(const string& p, int* badchar, vector<int>& suffix, bool* prefix){ // Implementation details omitted. } bool boyermoore_search(string s, string t){ const int MAX_CHAR=256; int badchar[MAX_CHAR]; memset(badchar,-1,sizeof(badchar)); vector<int>suffix(t.size()); bool prefix[t.size()]; memset(prefix,false,sizeof(prefix)); bm_preprocess(t,badchar,suffix,prefix); int shift=t.size(); int pos=s.size()-t.size(); while(pos>=0){ int j=t.size()-1; while(j>=0 && t[j]==s[pos+j]) j--; if(j<0){ cout<<"Found at position "<<pos<<endl; pos=pos+t.size()-prefix[0]?1:suffix[0]+1; } else{ int x=j-badchar[s[pos+j]]; int y=((shift>j+1)?1:j+2-suffix[j]); pos=pos+x>y?x:y; } } return false; } ``` ---