数据结构--KMP算法
作者:
黎虽无意逐鹿
,
2024-03-26 16:04:20
,
所有人可见
,
阅读 7
void get_next(string sub,int next[])
{
int i = 1, j = 0;
next[1] = 0;
while(i < sub.length)
{
if(j == 0 || sub.ch[i] == sub.ch[j])
{
i++,j++;
next[i] = j; //若p_i == p_j 则next[j+1] = next[j]+1
}
else
j = next[j]//否则令 j = next[j]
}
}
int KMP(string s,string sub,int next[])
{
int i = 1; j = 1;
while(i <= s.length && j <= sub.length)
{
if (j == 0 || s.ch[i] == sub.ch[j])
i++,j++;//继续比较字串
else
j = next[j];//模式串向右移动
}
if(j > sub.length)
return i-sub.length;//匹配成功
else
return 0;
}
void get_nextval(string sub,int nextval[])
{
int i=1,j=0;
nextval[1] = 0;
while(i<sub.length)
{
if(j==0 || sub.ch[i] == sub.ch[j])
{
++i,++j;
if(sub.ch[i]!=sub.ch[j])nextval[i] = j;
else nextval[i] = nextval[j];
}
else
j = nextval[j];
}
}