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