字符串匹配(滚动Hash)

千公子

1. #include <iostream>
   
2. #include <string>
   
3. #include <cstring>
   
4. #include <cmath>
   
5. 
   
6. const int seed = 31;
   
7. using namespace std;
   
8. 
   
9. long long hash(string &s)
   
10. {
    
11.     long long hash_code = 0;
    
12.     for(int i=0; i<s.size()-1; ++i){
    
13.         hash_code = ((hash_code + s.at(i)) * seed) % __LONG_LONG_MAX__;
    
14.     }
    
15.     hash_code = (hash_code + s.at(s.size()-1)) % __LONG_LONG_MAX__;
    
16.     return hash_code;
    
17. }
    
18. 
    
19. void RabinKarp(string &source, string &pattern)
    
20. {
    
21.         if(source.size()<pattern.size())
    
22.         {
    
23.                 cout << "Error" << endl;
    
24.                 return;
    
25.         }
    
26.         long long hash_pattern = hash(pattern);
    
27.         long long old_hash = 0;
    
28.         string begin = source.substr(0, pattern.size());
    
29.         old_hash = hash(begin);
    
30.         if(old_hash == hash_pattern)
    
31.                 cout << "begin_index: " << 0 << endl;
    
32.         for(int i=1; i<=source.size()-pattern.size(); ++i)
    
33.         {
    
34.                 old_hash = (old_hash - source.at(i-1) * pow(seed, pattern.size()-1)) * seed + source.at(i+pattern.size()-1);
    
35.                 if(old_hash == hash_pattern)
    
36.                         cout << "begin_index: " << i << endl;
    
37.         }       
    
38. }
    
39. 
    
40. int main()
    
41. {
    
42.         string a, b;
    
43.         cin >> a >> b;
    
44.         RabinKarp(a, b);       
    
45.     return 0;
    
46. }
    

复制代码