BF算法(蛮力匹配)
2019-10-16 07:51:18来源:博客园 阅读 ()
BF算法(蛮力匹配)
输入主串a,模式b
b在a中的位置
1.在串a和串b中设置比较的下标i=0,j=0;
2.重复下述操作,直到a或b的所有字符均比较完毕:
2.1如果a[i]等于b[i],继续比较a和b的下一对字符;
2.2负责,下标i和j分别回溯,开始下一趟匹配;
3.如果b中所有字符均比较完,则匹配成功,返回本趟匹配的起始位置;负责匹配失败,返回0;
#include<iostream> #define N 100000 using namespace std; char a[N],b[N]; int BF(char a[],char b[])//BF算法 { int i = 0,j = 0;//i,j变量分别表示在主串和模式串的位置 int start = 0;//start记录主串回溯的位置 while(a[i] != '\0' && b[j] != '\0') { if(a[i] == b[j]) { i++; j++; } else { start++; i = start; j = 0; } } if(b[j] == '\0')//如果是模式串所有匹配完成,即匹配成功,返回位置 return start + 1; else//否则匹配失败 return 0; } int main() { int t; cin >> t;//t个测试样例 while(t--) { int flag;//模式匹配成功的位置 cin >> a >> b;//读入字符串 flag = BF(a,b); cout << flag << endl; } return 0; }
原文链接:https://www.cnblogs.com/biaobiao88/p/11669826.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash