BF 算法总感觉写法怪怪的，改了一下
欢迎拍砖哈，代码个数 可使用 codeblok 格式化一下：算法学起来比较吃力。。。:cry#include <stdio.h>
#include <stdlib.h>
typedef char* String;
// 返回子串T在主串S中第pos个字符之后的位置
// 若不存在，则返回0
// T非空，1 <= pos <= strlen(S)
int index(String S, String T, int pos)
{
int i = pos;
int j = 0;
int lenS = strlen(S);
int lenT = strlen(T);
while(i<lenS && j<lenT) {
if(S == T) { // 判断下一个
i++;
j++;
} else { // 回溯
i = i-j+1;
j = 0;
}
}
if(j > lenT - 1) {
return i - lenT;
} else {
return -1;
}
}
int main()
{
int i;
i = index("Helloo", "lo", 0);
printf("index: %d", i);
return 0;
}
一般编程语言，都是 返回 -1 表示匹配不到的意思。 修改好的 KMP 算法：#include <stdio.h>
#include <stdlib.h>
typedef char* String;
// KMP 算法start
/*
获取 KMP 的 next 数组
*/
void getNext(String T, int *next)
{
int j = -1;// 前
int i = 0;// 后
next = -1; // next数组第一个元素为-1
int lenT = strlen(T); // 字符串长度
while( i < lenT)
{
// 刚开始or匹配相等加1向前走（BF原則）
if(-1==j || T == T)
{
j++;
i++;
if(T != T)
{
next = j; // 填下一个
}
else
{
next = next;
}
}
else
{
j = next;
}
}
}
// 返回子串T在主串S第pos个字符之后的位置
// 若存在，返回-1
int indexKMP(String S, String T, int pos)
{
int i = pos;
int j = 0;
int next;
getNext(T, next); // 获取next数组
int lenS = strlen(S);
int lenT = strlen(T);
while(i<lenS && j<lenT)
{
if(-1 == j || S == T) //j=-1，没有这个元素，指向下一个元素，类似BF算法
{
i++;
j++;
}
else // 匹配失败
{
j = next;
}
}
if(j > lenT - 1)
{
return i - lenT;
}
else
{
return -1;
}
}
// KMP 算法end
int main()
{
i =indexKMP("ababaaabacca", "aaaa", 0);
printf("KMP, index: %d ", i);
printf("\n");
return 0;
}
4#说的啥、
页:
[1]