BF(朴素算法)
BF.c(字符数组从0开始)
- Index_BF函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17int Index_BF(char * a, char * b)
{
int i=0, j=0;
// 遍历两个字符串,都不为空继续执行
while( *(a+i) && *(b+j) )
{
// 如果对应字符相等,继续执行
if(*(a+i) == *(b+j)) {i++; j++;}
// 否则i后移一位,j回到头位置
else{i=i-j+1; j=0;}
}
// 如果*(b+j)=='\0',则在a中有b,返回第一次出现的位置
if(!*(b+j)) return i-j+1;
// 否则返回-1
else return -1;
} - 主函数main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 若b字符串在a中,返回b第一次出现的次序
int Index_BF(char * a, char * b);
int main(void)
{
char *a = "I know, sgy is handsome!";
char *b = "sgy";
int loc = Index_BF(a, b);
printf("%d\n",loc);
return 0;
} - 输出
1
9
KMP算法
难点——求next数组
- 求next数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void getNext(Str substr, int next[])
{
int j = 1, t = 0;
next[1] = 0;
while(j < substr.length)
{
if(t == 0 || substr.ch[j] == substr.ch[t])
{
next[j+1] = t+1;
++t;
++j;
}
else
t = next[t];
}
}
优化——求nextval数组
- 求nextval数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void getNextval(Str substr, int nextval[])
{
int j = 1, t = 0;
nextval[1] = 0;
while(j < substr.length)
{
if(t==0 || substr.ch[j] == substr.ch[t])
{
if(substr.ch[j+1] != substr.ch[t+1])
nextval[j+1] = t + 1;
else
nextval[j+1] = nextval[t+1];
++j; ++t;
}
else
t = nextval[t];
}
}
实现——测试
- KMP函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18int KMP(Str str, Str substr, int nextval[])
{
int i = 1, j = 1;
while(i <= str.length && j <= substr.length)
{
if(j == 0 || str.ch[i] == substr.ch[j])
{
++i;
++j;
}
else
j = nextval[j];
}
if(j > substr.length)
return i - substr.length;
else
return 0;
} - 主函数main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int KMP(Str str, Str substr, int nextval[]);
void getNext(Str substr, int next[]);
void getNextval(Str substr, int nextval[]);
// 本例都是下标从1开始存储
int main(void)
{
char *a = " I know, sgy is handsome!";
char *b = " sgy";
Str str, substr;
if(1 == strAssign(&str, a) && 1 == strAssign(&substr, b))
{
int nextval[substr.length];
getNextval(substr, nextval);
int i = 0;
int loc = KMP(str, substr, nextval);
printf("location = %d\n", loc);
}
return 0;
} - 输出
1
location = 9
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 年轻没有梦!
评论