#include<stdio.h>
#include<stdlib.h>
#define N 25
#include<string.h>
/*
前缀：除了最后一个字符以外，一个字符串的全部头部组合
后缀：除了第一个字符以外，一个字符串的全部尾部组合
注：子串和主串存在许多的部分匹配的情况下才体现出他的优势
*/
void GetNext(int next[], char *str)
{
next[0] = -1;
next[1] = 0;
int j = 0;//每次指向前缀的后一个不匹配的字符
int i = 2;//i指向待计算的next的字符
int len = strlen(str);
while (i < len)
{
if (j == -1||str[j] == str[i- 1])
next[i++] = ++j;
else
j = next[j];
}
for (int i = 0; i < len; ++i)
{
printf("M", next[i]);
}
getchar();
}
int KMP(char *str, char *sub)
{
int next[128] = {0};
GetNext(next, sub);
int str_len = strlen(str);
int sub_len = strlen(sub);
int i = 0;
int j = 0;
while(i < str_len && j < sub_len)
{
if (j == -1 ||str[i] == sub[j])
{//子串的第一个字符没匹配上的时候j==-1
//其他情况都大于-1
i++;
j++;
}
else
j = next[j];
}
if (j == sub_len)
return i - j;
else
return -1;
}
void main()
{
char *str="abcabcb";
//-100012340
char *sub="abcb";
printf("%d",KMP(str, sub));
}
