【数据结构】kmp算法介绍+模板代码
目录
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;
else
return 0;
}