本文是结合刘大有主编《数据结构》所写笔记,如果想学习kmp.推荐
http://blog.csdn.net/china8848/archive/2008/04/29/2342243.aspx下面的估计我都看不懂
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
int f[100];
void createf(string pat)//find数组
{
memset(f,0,sizeof(f));
int m=pat.size();
f[0]=-1;
for(int j=1;j<m;j++)
{
int i=f[j-1];
while(pat[j]!=pat[i+1]&&i>=0)//只要p[j]与p[i+1]不等,则递推计算i
i=f[i];
if(pat[j]==pat[i+1])
f[j]=i+1;
else
f[j]=-1;
}
}
/* 已知f[13]=6;acbacbcacbacb,求f[14]acbacbcacbacb
a则先判断pat[6+1]是否等于pat[14],不等
再判断 i=f[6]acbacb=3;判断pat[14]pat[3+1]相等,则i=3
可得f[j]=3+1;
*/
int kmp(string pat,string str)//求pat在str中的第一个匹配的起点
{
int p=0,s=0;
createf(pat);
int m=pat.size();
int n=str.size();
while(p<m&&s<n)
{
if(pat[p]==str[s])
{
p++;s++;
}
else
{
if(p==0)s++;
else
p=f[p-1]+1;//s无需变化,举例,abababababba
/* |
s指向a
ababb
// |
// p指向b,s和p失配
abababababba
// |
s s不变
由于ab=ab,既f[p-1]=2 ababb
// p=f[p-1]+1=3 |
// p 回到f[p-1]+1的位置;
相等,则s和p都加1.
//
*/
}
}
if(p<m)
return -1;
return s-m;
}
int main()
{
//freopen("s.txt","r",stdin);
//freopen("key.txt","w",stdout);
cout<<kmp("fgfh","abcabfgfdhsfgfhdfdfhfcdab");//返回的是数组下标,从0开始
getchar();
//system("PAUSE");
return 0;
}
改进的kmp
----------------------以下是原kmp生成next值的算法---------------------
void createf(string pat)//find数组
{
memset(f,0,sizeof(f));
int m=pat.size();
f[0]=-1;
for(int j=1;j<m;j++)
{
int i=f[j-1];
while(pat[j]!=pat[i+1]&&i>=0)//只要p[j]与p[i+1]不等,则递推计算i
i=f[i];
if(pat[j]==pat[i+1])
f[j]=i+1;
else
f[j]=-1;
}
}
/* 已知f[13]=6;acbacbcacbacb,求f[14]acbacbcacbacba则先判断pat[6+1]是否等于pat[14],不等
再判断 i=f[6]acbacb=3;判断pat[14]pat[3+1]相等,则i=3
可得f[j]=3+1;
*/
-------------------以下还是未改进kmp------------
void get_next(String T,int &next[])
{
i=1;j=0;next[1]=0;
while(i<=T.Length)
{
if(j==0 || T[i]==T[j]){++i;++j; next[i]=j;/**********(2)*/}
else j=next[j];
}
}
--------------------以下是改进型----------
上面的f[j]相当于next[]
int i,j,len,n;
len=strlen(s);
//KMP构造
i=0,j=-1;
next[0]=-1;
while(i<len)
{
if(j==-1||s[i]==s[j])
{
i++,j++;
if(s[i]!=s[j])
next[i]=j;
else
next[i]=next[j];
// printf("next[%d]=%d\n",i,next[i]);
}
else j=next[j];
}
posted on 2009-06-30 14:12
luis 阅读(606)
评论(0) 编辑 收藏 引用 所属分类:
规律