kmp算法中next[i]=j;这行什么意思啊
void next(const char* p,int* nextVal)
{
int i=0,j=-1;
int plen = strlen(p);
nextVal[0]=-1;
while(i <plen)
{
if(j==-1 || p[i]==p[j])
{
++i;++j;
if(p[i]!=p[j])
{
nextVal[i]=j;
}
else
{
nextVal[i]=nextVal[j];
}
}
else
j=nextVal[j];
}
}
其中这一行代码死活看不明白：nextVal[i]=j;怎么知道nextVal[i]的值是j的呢？书看了半天也没看明白。请牛人指点啊
[解决办法]
next数组里存放的是如果在该位置比较失败，回退到那个位置跟输入串的下一个位置继续比较。
当p[i]!=p[j]的时候，如果真有字符串在此比较失败，说明只要回退到j这个位置，因为此时[0,j-1]都是相等的，而第j个位置还有可能和第i个位置相等。
而当p[i]==p[j]的时候，如果有字符串在此比较失败的话，说明尽管[0,j-1]还是相等，可是第j的位置永远不可能跟第i个位置相等了。
[解决办法]
void GetNext(char* T, int* next)
{
int j = 0;
int k = -1;
int Len = strlen(T);
while (j < Len)
if ((k == -1) || (T[k] == T[j]))
{
j++;
k++;
next[j-1] = k + 1;
}
else
k = next[k] - 1;
}
[解决办法]
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <windows.h>
void strNext(const char *modstr,int next[])
{
int i = 1;
int j = 0;
next[0] = 0;
while(i < (int)strlen(modstr))
{
if(modstr[i]==modstr[j])
{
next[i] = j;i++;j++;
}
else if(j == 0)
{
next[i] = 0;
i++;
}
else
{
j = next[i];
}
}
return;
}
int main()
{
int next[20];
int i = 0,j = 0;
char *compareString = "bacbbacbaabcca";
char *modelString = "bacba";
memset(next,0,sizeof(next));
strNext(modelString,next);
while(i < (int)strlen(compareString))
{
if(j == (int)strlen(modelString))
{
printf("there exist a str\n");
return 0;
}
if(compareString[i] == modelString[j]) {i++;j++;}
else
{j = next[j];i++;}
}
printf("there isn't exist a str\n");
return 0;
}
