字符串处理是每个编程者都必须掌握的知识，主要看看字符串的搜索查找功能。
现在的编程语言如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 }
执行输出：
