王道計算機考研 數(shù)據(jù)結(jié)構(gòu)
void nextArr(const char* sub, int* next)
{
int len = strlen(sub);
next[0] = -1;
next[1] = 0;
int i = 2;
int k = 0;
while (i < len)
{
if (k == -1 || sub[i - 1] == sub[k])
{
next[i] = k + 1;
k++;
i++;
}
else
{
k = next[k];
}
}
}
int * nextValArr(int* next,int lenSub,const char?*sub,int *nextVal)
{
nextVal[0] = -1;
for (int j = 1; j < lenSub; j++)
{
if (sub[j] == sub[next[j]])
{
nextVal[j] = next[next[j]];
}
else
{
nextVal[j] == next[j];
}
}
return nextVal;
}
int Kmp(const char* str, const char* sub)
{
if (sub == "")
return 0;
int i = 0;
int j = 0;
int lenStr = strlen(str);
int lenSub = strlen(sub);
if (lenSub == 1)
{
for (int a = 0; a < lenStr; a++)
{
if (str[a] == sub[0])
return a;
}
return -1;
}
int* next = (int*)malloc(sizeof(int) * lenSub);
nextArr(sub, next);
int* nextVal = (int*)malloc(sizeof(int) * lenSub);
nextVal = nextValArr(next, lenSub,sub,nextVal);
while (i < lenStr && j < lenSub)
{
if ((j == -1) || str[i] == sub[j])
{
i++;
j++;
}
else
{
j = nextVal[j];
}
}
free(next);
if (j >= lenSub)
{
return i - j;
}
return -1;
}
自學(xué)一下午自己寫的KMP
