一、问题引入
模式匹配算法是对两个字符串进行比较匹配的算法。
在两个串中字符逐个匹配，若完全匹配，则返回位置，否则返回-1。
二、解决过程
2-1 函数：index_bf()
int index_bf(char *S, char *T, int pos)
{
int S_len = strlen(S);
int T_len = strlen(T);
if (S_len == 0 || T_len == 0)
return -1;
if (pos < 0 || pos > S_len-1)
return -1;
int i = pos, j = 0;
while (i < S_len && j < T_len)
{
if (S[i] == T[j])
{
++i;
++j;
}
else
{
i = i - j + 1; // i 移到最近一次相等的位置
j = 0; // j 移到起点位置
}
}
if(j >= T_len) // 若字符串S和T全部比较完后，且j的位置移到T的末尾，则匹配成功
return (i - T_len);
else
return -1;
}
2-2 函数：main()
#include <stdio.h>
int main(void)
{
char S[] = {"hello world"};
char T[] = {"heo"};
int index; // index从0开始
printf("S_String：%sn", S);
printf("T_String：%sn", T);
if (-1 == ( index = index_bf(S, T, 0)))
{
printf("Not foundn");
}
else
{
printf("Found, index is %dn", index);
}
return 0;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
