串匹配算法之BM算法
参考资料:
http://blog.csdn.net/eric491179912/article/details/6210009
http://blog.163.com/pengfeicui@yeah/blog/static/106403250201092681158650/
这里,我们仅仅用了坏字符规则
定义一个滑动距离函数:
dist(C)= 1) m – j j = max{j| tj = c && 1<= j <= m - 1}
2) m 若C不出现在模式中或tm = c
比如 T = pattern dist(a)= 7 – 2 ; dist(t) = 7 – 4 (算最后出现的) ; dist(e) = 7 – 5 ; dist(r) = 7 - 6;
最后一个dist(n) = 7 (m ,模式串T的总长度) ,其他的未出现的字符, dist(ch) = 7;
程序如下:
1: void BMDist(string str,int dist[])
2: {
3: int i;
4: for (i = 0; i < 256; i++)
5: {
6: dist[i] = str.length();
7: }
8: for (i = 0; i < str.length() - 1; i++)//最后一个字符取不到
9: {
10: dist[str[i]] = str.length() - i - 1;
11: }
12: dist[str[str.length()-1]] = str.length();
13:
14: }
15:
16: int BM(string s, string t,int dist[])
17: {
18: int i = t.length();
19: while(i <= s.length())
20: {
21: int j = t.length();
22: while(j>0 && s[i-1]==t[j-1])
23: {
24: j--;
25: i--;
26: }
27: if (j == 0)
28: {
29: return i + 1;
30: }
31: else
32: {
33: i = i + dist[s[i-1]];
34: }
35: }
36: return -1;
37: }
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
测试代码:
1: int main()
2:
3: {
4:
5: while(1)
6: {
7: clock_t start,stop;
8: string Str,Tsr;
9:
10: int flag1,flag2,flag3;
11: int dist[256];
12:
13: int next[1000]={0,};
14: cout <<"请输入S串与T串:" <<endl;
15: cin >> Str >> Tsr;
16: cout << endl;
17:
18: start = clock();
19: for (int i=0; i< 1000; i++)
20: {
21: flag1 = BF(Str,Tsr);
22: }
23: stop = clock();
24: cout << "BF算法的执行时间是:"<< stop - start << endl;
25:
26:
27: start = clock();
28: for (int i=0; i< 1000; i++)
29: {
30: kmpNext(Tsr,next);
31: flag2 = kmp(Str,Tsr,next);
32: }
33: stop = clock();
34: cout << "KMP算法的执行时间是:"<< stop - start << endl;
35:
36:
37: start = clock();
38: for (int i=0; i< 1000; i++)
39: {
40: BMDist(Tsr,dist);
41: flag3 = BM(Str,Tsr,dist);
42: }
43: stop = clock();
44: cout << "BM算法的执行时间是:"<< stop - start << endl;
45:
46: if (flag1 == -1)
47: {
48: cout << "没有找到子串"<<endl;
49: }
50: else
51: {
52: cout << "找到子串的位置为"<< flag1 <<endl;
53: }
54: if (flag2 == -1)
55: {
56: cout << "没有找到子串"<<endl;
57: }
58: else
59: {
60: cout << "找到子串的位置为"<< flag2 <<endl;
61: }
62: if (flag3 == -1)
63: {
64: cout << "没有找到子串"<<endl;
65: }
66: else
67: {
68: cout << "找到子串的位置为"<< flag3 <<endl;
69: }
70: }
71:
72: return 0;
73: }
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
最新文章
- Lesson 17 Always young
- tftp-nfs开发环境搭建
- IOS开发之----#import、#include和@class的区别
- 我的权限系统设计实现MVC4 + WebAPI + EasyUI + Knockout(五)框架及Web项目的组件化
- 【BZOJ-3721】Final Bazarek 贪心
- html5摇一摇[转]
- nc:a test cmd for TCP HTTP
- 文字垂直居中,水平居中 a标签水平居中只要给他的父级设置text-align=center
- UTF-8
- String的两个API,判断指定字符串是否包含另一字符串,在字符串中删除指定字符串。
- USACO 2014 Open Silver Fairphoto
- scip学习
- 【资料下载区】【iCore系列及其它模块相关文档】更新日期2017/07/24
- Codeforces gym 101343 A. On The Way to Lucky Plaza【概率+逆元+精度问题】
- java之面向对象的基础知识
- 显示器如何显示一个YUV422格式的图形
- BZOJ 1014 [JSOI2008]火星人prefix (Splay + Hash + 二分)
- Daily Scrumming* 2015.11.1(Day 13)
- AndroidUI多线程网络请求更新导致BUG
- SQL用例集锦
热门文章
- java EE技术体系——CLF平台API开发注意事项(2)——后端测试
- 【Go】Panic函数
- PHP_命名空间
- 项目记事【多线程】:关于 SimpledDateFormat 的多线程问题
- 【bzoj1014】[JSOI2008]火星人prefix Splay+Hash+二分
- 【bzoj3073】[Pa2011]Journeys 线段树优化建图+堆优化Dijkstra
- 【bzoj4260】Codechef REBXOR Trie树
- 常用的Java基本代码汇总
- 面向对象oop思想
- 【CCF】有趣的数 数位dp