闲来无事，实现了一下KMP算法，代码如下：
/**
* 由于KMP算法只预处理sub串，因此这种算法很适合这样的问题：给定一个sub串和一群不同的main串，
* 问sub是哪些main串的子串。
*/
/* kmp & cal_next，将不使用数字的索引0，从1开始使用 */
void kmp(char str_main[], int str_main_len, char str_sub[], int str_sub_len, int next[])
{
int j = 0;
int i = 0;
for (i = 1; i <= str_main_len; i++)
{
while (j > 0 && str_sub[j + 1] != str_main[i])
j = next[j];
if (str_sub[j +1] == str_main[i])
++j;
/* 匹配成功 */
if (j == str_sub_len)
{
printf("Pattern occurs with shift: %d/n", i - str_sub_len);
/* 继续匹配，可能有多处匹配 */
j = next[j];
}
}
}
void cal_next(char str_sub[], int str_sub_len, int next[])
{
int j = 0;
int i = 0;
next[1] = 0;
for (i = 2; i <= str_sub_len; i++)
{
while ( j > 0 && str_sub[j + 1] != str_sub[i])
j = next[j];
if (str_sub[j + 1] == str_sub[i])
j++;
next[i] = j;
}
}
/* kmp2 & cal_next2，将从索引0开始使用 */
void kmp2(char str_main[], char str_sub[], int next[])
{
int j = -1;
int i = 0;
int str_main_len = strlen(str_main);
int str_sub_len = strlen(str_sub);
for (i = 0; i < str_main_len; i++)
{
while (j >= 0 && str_sub[j + 1] != str_main[i])
j = next[j];
if (str_sub[j +1] == str_main[i])
j++;
/* 匹配成功 */
if (j == str_sub_len - 1)
{
printf("Pattern occurs with shift: %d/n", i - str_sub_len);
/* 继续匹配，可能有多处匹配 */
j = next[j];
}
}
}
void cal_next2(char str_sub[], int next[])
{
int j = -1;
int i = 0;
int str_sub_len = strlen(str_sub);
next[0] = -1;
j = -1;
for (i = 1; i < str_sub_len; i++)
{
while (j >= 0 && str_sub[j + 1] != str_sub[i])
j = next[j];
if (str_sub[j + 1] == str_sub[i])
j++;
next[i] = j;
}
}