求一个模式匹配的新算法及实现
急求个改进算法 或者KMP算法的改进算法 9命啊
[解决办法]
#include <iostream>
using namespace std;
#define MaxSize 50
typedef struct
{
char elem[MaxSize];
int len;
}SqString;
void Next(SqString substr, int next[]);
int
main(void)
{
void CreateString(SqString &str, const char *&p);
int KMP(SqString &hoststr, SqString &substr);
void DispString(SqString str);
const char *p1 = "abcdefghigklmn ";
const char *p2 = "higklmn ";
SqString hoststr, substr;
hoststr.len = substr.len = 0;
CreateString(hoststr, p1);
CreateString(substr, p2);
cout < < "hoststr is : " < <endl;
DispString(hoststr);
cout < <endl;
cout < < "substr is : " < <endl;
DispString(substr);
cout < <endl;
int location;
location = KMP(hoststr, substr);
if (location == -1)
cout < < "can 't find substring in hoststr! " < <endl;
else
cout < < "the location of substr in hoststr is : " < <\
location < <endl;
return 0;
}
void CreateString(SqString &str, const char *&p)
{
int i;
char ch;
i = 0;
ch = p[i];
while (ch != '\0 ')
{
str.elem[str.len] = ch;
str.len++;
i++;
ch = p[i];
}
}
void DispString(SqString str)
{
int i;
if (str.len <= 0)
{
cout < < "string is NULL! " < <endl;
return ;
}
for (i=0; i <str.len; i++)
cout < <str.elem[i];
cout < <endl;
}
void GetNext(SqString substr, int next[])
{
int j, k;
j = 0;
k = -1;
next[j] = -1;
while (j < substr.len)
{
if (k==-1 || substr.elem[j]==substr.elem[k])
{
j++;
k++;
next[j] = k;
}
else
k = next[k];
}
}
int KMP(SqString &hoststr, SqString &substr)
{
int next[MaxSize], i, j, v;
i = j = 0;
GetNext(substr, next);
while (i <hoststr.len && j <substr.len)
{
if (j==-1 || hoststr.elem[i]==substr.elem[j])
{
i++;
j++;
}
else
j = next[j];
}
if (j > = substr.len)
v = i-substr.len+1;
else
v = -1;
return v;
}
[解决办法]
kmb在一般情况下经理论和实际证明效果并不比传统的好多少:我有一个叫BM算法的你可看看.有兴趣可看我的blog
http://blog.csdn.net/jxnczyp
