Horspool 字符串匹配算法分析

不点 阅读:171 2020-10-19 15:34:57 评论:0

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

 程序运行:

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
关注我们

扫一扫关注我们,了解最新精彩内容