字符串匹配算法(BF KMP)
程序员文章站
2024-03-17 18:07:16
...
BF算法(朴素算法):
思路:
子串的定位操作通常称做模式匹配,其中子串称做模式串,主串称做目标串,朴素的模式匹配算法即是模式匹配的一种算法,其优点是简单易懂,易于理解,某些应用场合效率较高。缺点是需要多次回溯,对于数据较大的文本文件而言效率极低。
例子:
在BF算法中,失配时,主串中的i回退到每次起始位置的下一个位置,即i= i-j+1;子串中的j回退到起始位置,即j=0;当j遍历完子串都没有发生失配,此时匹配成功。
源代码:
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdio.h>
int BF(const char *str, const char *sub, int pos)//时间复杂度O(m*n)
{
assert(str != NULL && sub != NULL);
int lenstr = strlen(str);
int lensub = strlen(sub);
if (pos<0 || pos>lenstr)
{
return -1;
}
int i = pos;
int j = 0;
while (i < lenstr && j < lensub)
{
if (str[i] == sub[j])
{
i++;
j++;
}
else
{
i = i - j + 1;
j = 0;
}
}
if (j >= lensub)
{
return i - j;
}
else
{
return -1;
}
}
int main()
{
char *str = "ababcabcd";
char *sub = "abcd";
printf("%d\n", BF(str, sub, 0));
//printf("%d\n",KMP(str,sub,0));
return 0;
}
KMP算法(高效的匹配算法):
KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
例子:
在KMP算法中,主串中的i不回退。子串中的j回退,且每次回退的位置用next[]确定。
源代码:
void GetNext(int *next, char *sub)//用于找j回退的位置k
{
assert(next != NULL && sub != NULL);
int lensub = strlen(sub);
next[0] = -1;
next[1] = 0;
int j = 2;
int k = 0;
while (j < lensub-1)
{
if ((k == -1) || sub[k] == sub[j])//回退为-1时,k++
{
next[j] = k;
j++;
k++;
}
else
{
k = next[k];
}
}
}
int KMP(char *str, char *sub, int pos)//时间复杂度O(m+n)
{
assert(str != NULL && sub != NULL);
int lenstr = strlen(str);
int lensub = strlen(sub);
if (pos<0 || pos>lenstr)
{
return -1;
}
int *next = (int *)malloc(sizeof(int)*strlen(str));
assert(next != NULL);
GetNext(next, sub);
int i = pos;
int j = 0;
while (i < lenstr && j < lensub)
{
if ((j == -1) || str[i] == sub[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j >= lensub-1)
{
return i - j;
}
else
{
return -1;
}
}
int main()
{
char *str = "ababcabcdabcdef";
char *sub = "ef";
//printf("%d\n", BF(str, sub, 0));
printf("%d\n",KMP(str,sub,0));
return 0;
}
个人觉得,BF算法和KMP算法各有所长。BF算法时间复杂度为O(m*n),KMP的时间复杂度为O(m+n);但KMP的空间复杂度为O(n),因为它创建了一个next[],用于保存回退的值,BF算法空间复杂度为O(1)。
上一篇: KMP算法学习
下一篇: 多线程的一些基础内容