BF法就是brute force暴力法,就是在主串里面一个一个字符向后移去查找是否存在需要查找的子字符串。
第一种方法查找所有出现的字符串在主字符串里的下标:
vector<int> bfSearch(string &text, string &substr)
{
vector<int> begIndex;
int n = text.size();
int m = substr.size();
//注意这里是i<=n-m不是i<n-m
for (int i = 0; i <= n - m; i++)
{
int j = 0;
for (; j < m; j++)
{
if (substr[j] != text[i+j])
{
break;
}
}
if (j == m)
{
//注意这里是i,不是i-m
begIndex.push_back(i);
}
}
return begIndex;
}
测试:
int main()
{
string str1 = "abcddbeddbaddb";
string substr = "ddb";
vector<int> vi = bfSearch(str1, substr);
for(auto x:vi)
cout<<x<<" ";
cout<<endl;
system("pause");
return 0;
}
运行:
显式回溯,查找第一个出现的字符串在主串中的下标:
int bfSearchTrackBack(string &text, string &substr)
{
int n = text.size();
int m = substr.size();
int j = 0;
int i = 0;
for (; i<=n-m && j<m; i++)
{
if (text[i] == substr[j])
{
j++;
}
else
{
i = i-j; //回溯,后面还有i++,所以这里不用+1.
j = 0;
}
}
if (j == m)
return i-m;
return n;
}
测试:
int main()
{
string str1 = "abcddbeddbaddb";
string substr = "ddb";
cout<<bfSearchTrackBack(str1, substr)<<endl;
system("pause");
return 0;
}
运行:
分享到:
相关推荐
给定一段文本,在该文本中查找并定位任意给定字符串。 要求: (1)实现BF算法; (2) 实现BF算法的改进算法:KMP算法 2.采用分治法求解最大连续子序列和问题 给定一个有n(n≥1)个整数的序列,要求求出其中...
当然,你用上一节讲的 BF 算法和 RK 算法,也可以实现这个功能,但是在某些极端情况下,BF 算法性能会退化的比较严重,而 RK 算法需要用到哈希算法,而设计
18.2.8 string型字符串的查找 18.2.9 string型字符串的比較 18.2.10 判斷string型字符串是否為空 18.3 字符串的使用 18.3.1 swap() 交換兩個字符串的內容 18.3.2 將string型字符串轉為char型字符串 18.3.3 char型...
递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法 学习方法 观点:学习的目的还是掌握,然后应用 边学边练,“适度”刷题 多问、多思考、多互动 打怪升级学习法 知识...
这时窗口的变化都有一个显示的变化过程,如果你不喜欢这种显示过程的处理方式,也可以使这种视觉效果失效,选中HKEY_CURRENT_USER\Control Panel\Desktop\WindowMetrics,右键单击视窗右栏,新建字符串值,命名为...
(1)古典算法(Index_BF) (2)求Next 函数值(Get_next)和按Next 函数值进行匹配 (Index_KMP(next)) (3)求 Next 修正值(Get_nextval)和按 Next 修正值进行匹配(Index_KMP(nextval)) 5. 稀疏矩阵 (1)矩阵...
(1)古典算法(Index_BF) (2)求Next 函数值(Get_next)和按Next 函数值进行匹配 (Index_KMP(next)) (3)求 Next 修正值(Get_nextval)和按 Next 修正值进行匹配(Index_KMP(nextval)) 5. 稀疏矩阵 (1)矩阵...
style="background:#98bf21;height:100px;width:100px;position:relative"> jQuery 隐藏和显示 通过 hide() 和 show() 两个函数,jQuery 支持对 HTML 元素的隐藏和显示: 实例 $("#hide").click(function(){ $...
“(“变量名字符串”)”都变成对应GB码的十六进制字符。这样,标识符就符合规范了,即,由字母数字和下划线组成,并且由字母或下划线开始。例如:“nameof("示例变量")”替换后就是“nameof2822CABEC0FDB1E4C1BF2229...
###ver2.61(2014.7.12) ... #### 1.... - Kodexplorer为千帆网络工作室开发的一款服务器文件管理程序。 - 完美取代FTP管理:可用于服务器文件管理,...(字符串转义问题。1&#'[{'"+~%25\\\\ ////) - 文件编辑,添加收藏夹 -...