KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为T),如果它在一个主串(接下来称为S)中出现,就返回它的具体位置,否则返回-1(常用手段)。 假如是在串“SSSSSSSSSSSSSA”中查找“SSSSB”,设置两个指针i,j,比较到最后一个才知道不匹配,然后其中的i回溯,这个的效率是显然是最低的。大牛们是无法忍受“暴力破解”这种低效的手段的,于是他们研究出了KMP算法,其思想就如同我们上边所看到的一样:“利用已经部分匹配这个有效信息,保持i指针不回溯,通过修改j指针,让模式串尽量地移动到有效的位置。”所以,整个KMP的重点就在于当某一个字符与主串不匹配时,我们应该知道j指针要移动到哪?
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//打印一个数组
void print_array(int *a, int len)
{
int i;
for (i = 0; i < len; i++)
{
printf("%5d", a[i]);
}
printf("\n");
}
int str_index(const char *s, const char *t, int pos)
{
int i = pos;
int j = 0;
while (s[i] != '\0' && t[j]!= '\0')
{
if (s[i] == t[j])
{
i++;
j++;
}else
{
i = i - j + 1;
j = 0;
//printf("%d\n", i);
}
}
if (t[j] == '\0')
{
return i - j;
}else
{
return -1;
}
}
void get_next(const char *t, int *next, int len)
{
int j = 0;
int k = -1;
next[j] = -1;
while (t[j] != '\0')
{
if (k == -1 || t[j] == t[k])
{
next[++j] = ++k;
}else
{
k = next[k];
}
}
}
void get_next2(const char *t, int *next, int len)
{
int j = 0;
int k = -1;
next[j] = -1;
while (t[j] != '\0')
{
if (k == -1 || t[j] == t[k])
{
++j;
++k;
if (t[j] == t[k])
{
next[j] = next[k];
}else
{
next[j] = k;
}
}else
{
k = next[k];
}
}
}
int str_index_kmp(const char *s, const char *t, int pos)
{
int i = pos;
int j = 0;
int len = strlen(t);
int *next = (int *)malloc(sizeof(int) * (len + 1));
if (next == NULL)
{
printf("malloc failed\n");
exit(1);
}
get_next(t, next, len);
print_array(next, len);
get_next2(t, next, len);
print_array(next, len);
while (s[i] != '\0' && t[j]!= '\0')
{
if (s[i] == t[j])
{
i++;
j++;
}else if (j == 0)
{
i++;
}else
{
j = next[j];
printf("%d\n", i);
}
}
free(next);
if (t[j] == '\0')
{
return i - j;
}else
{
return -1;
}
}
int main()
{
int pos;
char buf[20] = "ABACCCCABABCDHI";
const char *t = "ABAB";
pos = str_index(buf, t, 0);
if (pos > 0)
{
printf("%s\n", buf + pos);
}
pos = str_index_kmp(buf, t, 0);
if (pos > 0)
{
printf("%s\n", buf + pos);
}
return 0;
}