Horspool 字符串匹配算法

Horspool 字符串匹配算法对Boyer-Moore算法的简化算法。

Horspool 算法是一种基于后缀匹配的方法,是一种“跳跃式”匹配算法,具有sub-linear亚线性时间复杂度

Horspool 算法:

  对于每个搜索窗口,该算法将窗口内的最后一个字符模式串中的最后一个字符进行比较。如果相等,则需要进行一个校验过程。该校验过程在搜索窗口中从后向前对文本和模式串进行比较,直到完全相等或者在某个字符处不匹配。无论匹配与否,都将根据字符d在模式串中的下一个出现位置将窗口向右移动

   可以使用下图进行理解:

  (1)窗口大小与模式串大小相同,窗口内容为文本内容的一部分。

  (2)对于窗口而言,每次从后向前匹配,直到全部相等(匹配),或者遇到不相等。

  (3)遇到不相等时,根据窗口中最后一个字符在模式串中的位置,窗口进行移动。如果模式串中有多个相同的字符,选择最后一个字符为准,以避免漏解。

  

代码(C++):

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 /**
 5 计算可跳转字符个数数组
 6 */
 7 int getDis(string &str,int *dis)
 8 {
 9     int len=str.length();
10     for (int i = 0; i < 256; i++)
11         dis[i]=len;    //最大跳跃字符数
12
13     for (int i = 0; i < len-1; i++)    //注意这里不包括最后一个
14         dis[str[i]]=len-1-i;
15     return 0;
16 }
17
18 /**
19 查找
20 */
21 int search(string &text,string &pattern,int *dis)
22 {
23     int j,pos;
24     bool tag=false;
25     int lenPattern=pattern.length();
26     int lenTrext=text.length();
27
28     j=0;
29     pos=0;
30     while(pos<=lenTrext-lenPattern)
31     {
32         j=lenPattern-1;
33         while(j>=0 && pattern[j]==text[pos+j])  //向前搜索
34             j--;
35         if(j==-1)
36         {
37             tag=true;
38             cout<<"The result is :"<<pos<<endl<<endl;
39             pos=pos+lenPattern;
40             continue;
41         }
42         else
43             pos=pos+dis[text[pos+lenPattern-1]];    //使用最后一个字符对齐的方法,进行“跳跃”移动
44     }
45     if(tag == false)    //不存在匹配
46         cout<<"-1"<<endl<<endl;
47     return 0;
48 }
49
50 int main()
51 {
52     int dis[256];
53     string text;
54     string pattern;
55     while(true)
56     {
57         cout<<"文本:";
58         cin>>text;
59         cout<<"模式:";
60         cin>>pattern;
61         getDis(pattern,dis);
62         search(text,pattern,dis);
63     }
64     return 0;
65 }

View Code

 程序运行:

时间: 2024-10-06 23:56:14

Horspool 字符串匹配算法的相关文章

c++ monte carlo 字符串匹配算法,

问题描述 c++ monte carlo 字符串匹配算法, monte carlo 字符串匹配 求代码,求注释啊.谢谢好心人

带有通配符的字符串匹配算法

问题描述 带有通配符的字符串匹配算法 C/C++实现 之前面试.遇见一个字符串匹配问题. 大概是这样的: 正常的匹配就不说了, 第一,'*'可以代表连续多个字符. 第二,'a+'可以代表'aa', 'aaa', 'aaaa'.....类推. 第三,'.'代表一个任意字符(非*, +): 字符串str,模式串假设名为mdstr; 我当时想的是str,mdstr都是有'*",等符号的. 后来觉得str应该没有* 我给出了一个可行的算法.暂不提,后来面试官说.两个字符串都允许*. 谁能提供一个思路.考

字符串匹配算法之BF(Brute-Force)算法

蛮力搜索,比较简单的一种字符串匹配算法,在处理简单的数据时候就可以用这种算法,完全匹配,就是速度慢啊. 基本思想 从目标串s 的第一个字符起和模式串t的第一个字符进行比较,若相等,则继续逐个比较后续字符,否则从串s的第二个字符起再重新和串t进行比较.  依此类推,直至串t 中的每个字符依次和串s的一个连续的字符序列相等,则称模式匹配成功,此时串t的第一个字符在串s 中的位置就是t 在s中的位置,否则模式匹配不成功. 具体实现 int BFindex(String S, String T) { i

最简单的php中字符串匹配算法教程

本文实例讲述了php中最简单的字符串匹配算法,具体实现方法如下:  代码如下 复制代码 <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)          (O)   3.  

php中最简单的字符串匹配算法_php技巧

本文实例讲述了php中最简单的字符串匹配算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)         

php中单字符串匹配算法实例

   代码如下 复制代码 <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)          (O)   3.          4.          5. ababcabc

字符串匹配算法之SimHash算法

由于实验室和互联网基本没啥关系,也就从来没有关注过数据挖掘相关的东西.在实际工作中,第一次接触到匹配和聚类等工作,虽然用一些简单的匹配算法可以做小数据的聚类,但数据量达到一定的时候就束手无策了. 所以,趁着周末把这方面的东西看了看,做个笔记. 来历 google的论文"detecting near-duplicates for web crawling"--------simhash. Google采用这种算法来解决万亿级别的网页的去重任务. 基本思想 simhash算法的主要思想是降

字符串匹配算法之KMP&amp;Boyer-Moore

KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候所需移动的下一个位置,直到达到字符串的末尾.KMP&Boyer-Moore算法是通过"字符串"与"搜索词"头部对齐,从尾部开始比较的一种方法. KMP   对于两个字符串: 1.用短的字符串的第一个字符开始依次与另外一个字符串进行比较 2.如果相同,继续比较下一位置的字符,否则,向后移动一定的距离(已经匹配上的字符个数-已经匹配字符串前缀和后缀对称的位数) 3.直到字符串的最后一位   Boyer-M

关于字符串操作的算法题目

原题链接: http://oj.leetcode.com/problems/interleaving-string/ 这是一道关于字符串操作的题目,要求是判断一个字符串能不能由两个字符串按照他们自己的顺序,每次挑取两个串中的一个字符来构造出来. 像这种判断能否按照某种规则来完成求是否或者某个量的题目,很容易会想到用动态规划来实现. 先说说维护量,res[i][j]表示用s1的前i个字符和s2的前j个字符能不能按照规则表示出s3的前i+j个字符,如此最后结果就是res[s1.length()][s