目錄

1.kmp算法介紹

2.應用場景

3.KMP與暴力算法比較

4.模板代碼

---

KMP算法是一種高效的字符串匹配算法，用于在文本串中快速查找模式串的所有出現位置。其核心思想是通過預處理模式串，避免在匹配失敗時進行不必要的回溯，從而將時間復雜度優化至?O(n + m)（n為文本長度，m為模式串長度）。

2.應用場景

• 大規模文本中的高效匹配（如編輯器、病毒掃描）。

• 多次使用同一模式串時的預處理優勢。

• 需要線性時間復雜度的場景（如實時處理）。

3.KMP與暴力算法比較

特性	KMP算法	暴力算法
文本指針	無需回退	可能多次回退
時間復雜度	O(n + m)	O(n*m)
空間復雜度	O(m)（存儲LPS數組）	O(1)

4.模板代碼

void getnext(char *p)
{int lenp=strlen(p);nextt[0]=-1;int k=-1;int j=0;while(j<lenp-1){if(k==-1||p[j]==p[k]){j++;k++;nextt[j]=k;}else{k=nextt[k];}}return;
}int KMP(char *s,char *p)
{int i=0;int j=0;int lens=strlen(s);int lenp=strlen(p);while(i<lens&&j<lenp){if(j==-1||s[i]==p[j]){j++;i++;}else{j=nextt[j];}}if(j==lenp)return 1;elsereturn 0; 
}