本文主要是介绍串及BF算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.串的相关定义
1.字符串的拷贝,比较,链接等等(C语言)
2 串:用' '引起来的字符序列,例如'abcd' (区别字符串"abcd")
3.空串:'' (区别字符串"")
4.子串:包含空串和本身,'abc'的子串:'','a','b','c','ab','bc','abc'7个
5.真子串:包含空串,不包含本身,'abc'的子串:'','a','b','c','ab','bc',6个
6.串的长度:串中字符的数目,例如'abc'的长度为3;
7.空格串:由一个或者多个空格组成的串' '
8.空串:零个字符的串称为空串''
二.BF(朴素查找算法)
1.字符串的查找举例:
"ababcabcdabcde"主串
"abcd"字串
2.查找算法定义:
在主串str的pos位置查找子串sub,找到返回下标,没有找到返回-1;其实就是要用到字符串的查找匹配算法.
3.BF算法(BF朴素查找算法)分析:
i不回退对吗?
举例:
主串:aaaaab
子串:aaaab
得出结论:i必须要回退,否则有可能错误,其实就是i不回退,是错误的.
4.BF算法思想:
相等则继续比较,不相等即查找失败则回退,回退是i(主串的下标)退到刚才的位置的下一个,j退到0 //成功返回字串在主串中的下标,失败返回-1
pos:开始查找的主串下标;
5.BF算法的实现
int BF(const char* str, const char* sub, int pos)
{assert(str != NULL && sub != NULL);if (str == NULL || sub == NULL||pos<0||pos>strlen(str)){return -1;}int i = pos;int j = 0;int lenstr = strlen(str);int lensub = strlen(sub);while (i < lenstr && j < lensub){if (str[i] == sub[j])//相等,往后走{i++;j++;}else//不相等,i回退到刚才的位置的下一个,j回退到0{i = i - j + 1;//重点j = 0;}}//利用子串是否遍历完成,来判断查找是否成功.注意:不能利用主串来判断if (j >= lensub){return i - j;}else{return -1;}}int main()
{const char* str1 = "ababcabcdabcde";//主串const char* str2 = "abcd";//子串printf("%d\n", BF(str1, str2, 10));
}6.BF算法的总结
1)在主串str的pos位置查找子串sub,找到返回下标,没有找到返回-1;
2)思想:相等则继续比较,不相等则回退,回退是i退到刚才的位置的下一个(i-j+1),j退到0
3)利用子串是否遍历完成,来判断查找是否成功,注意:不能利用主串来判断;
4).算法时间复杂度BF:O(n*m)
这篇关于串及BF算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
