字符串处理是每个编程者都必须掌握的知识,主要看看字符串的搜索查找功能。

现在的编程语言如C/C++/Java等都提供了对字符串子串的查找功能,具体如下:

(1)C:strchr,strstr。

(2)C++:find,rfind,find_first_of,find_first_not_of等等。

(3)Java:indexOf,lastIndexOf等。

 

下面说明一种使用递归哈希进行字符串搜索/查找的方法:

(1)递归哈希

  维护一个窗口,大小为n。如下公式即为起始位置为x,长度为n的窗口的哈希数值。

  递归哈希主要体现在哈希数值的更新操作,减少重复的计算。下面是递归哈希的更新公式。

  

因为窗口[x,x+n)与[x+1,x+n+1)有n个相同的字符,在上的更新公式中我们可以看到,更新就是把“头元素”的哈希数值去掉,在加上一个新增的窗口元素。

(2)使用递归哈希进行字符串匹配

  设模式串为pattern,文本为text,设定窗口大小Plen与模式串的长度相同。每次保持文本中Plen长度字符串的哈希值,当哈希值与模式串的哈希值相等时,进行字符串的具体校验。如果校验相等,报告结果。

 1 /* 
 2 使用递归哈希进行字符串精确匹配 
 3 */ 
 4 #include<iostream> 
 5 #include <string> 
 6 #define Q 13 
 7 #define MOD 5549873 
 8 using namespace std; 
 9  
10 /* 
11 初始化哈希值 
12 str:要计算哈希数值的字符串 
13 */ 
14 unsigned long recHash(const string &str){ 
15     unsigned long hash =0; 
16     for(int i=0;i<str.size();i++) 
17         hash=(hash*Q+str[i])%MOD; 
18     return hash%MOD; 
19 } 
20  
21 /* 
22 校验阶段 
23 text:带匹配文本 
24 pattern:模式 
25 pos:模式在文本中最后一个字符的位置 
26 */ 
27 int isverify(const string &text,const string &pattern,int pos){ 
28     string sub_str=text.substr(pos-pattern.size()+1,pattern.size()); 
29     if(sub_str == pattern){ 
30         cout<<"模式位置:"<<pos-pattern.size()+1<<endl; 
31         return 1; 
32     } 
33     return 0; 
34 } 
35  
36 /* 
37 text:带匹配文本 
38 pattern:模式 
39 Phash:模式对应的哈希值 
40 */ 
41 int match(const string &text,const string &pattern,const unsigned long Phash){ 
42     int Tlen=text.size(); 
43     int Plen=pattern.size(); 
44     bool tag=false; 
45     if(Tlen<Plen){ 
46         cout<<"文本中没有模式存在!!!"<<endl; 
47         return 0; 
48     } 
49  
50     unsigned long exp=1; 
51     for(int i=0;i<Plen-1;i++) 
52         exp=(exp*Q)%MOD; 
53  
54     unsigned long Thash=recHash(text.substr(0,Plen)); 
55     if(Thash == Phash && isverify(text,pattern,Plen-1)) 
56         tag=true; 
57  
58     int pos=Plen; 
59     while(pos<Tlen){ 
60         Thash=((Thash+MOD-(text[pos-Plen]*exp)%MOD)%MOD*Q+text[pos])%MOD; 
61         if(Thash == Phash && isverify(text,pattern,pos)) 
62             tag=true; 
63         pos++; 
64     } 
65  
66     if(!tag) 
67         cout<<"文本中没有模式存在!!!"<<endl; 
68     return 0; 
69 } 
70  
71 int main(){ 
72     string pattern; 
73     string text; 
74     while(true){ 
75         cout<<"要查找的模式:"<<endl; 
76         cin>>pattern; 
77  
78         cout<<"待匹配的文本:"<<endl; 
79         cin>>text; 
80  
81         cout<<"结果:"<<endl; 
82         match(text,pattern,recHash(pattern)); 
83         cout<<endl; 
84     } 
85     return 0; 
86 }
View Code

执行输出:

 

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Horspool 字符串匹配算法讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。