利用哈希表的思想实现字符串匹配函数

前言

C语言有一个字符串匹配函数strstr(const char source,const char pattern)，可以获取匹配字符串在源字符串的位置。我们今天利用哈希表的思想来实现这个函数。

例子

源字符串：“abccbasd” 匹配字符串：“ccba”

做法

我们可以求出匹配字符串的hashCode，至于如何求，我们可以定义自己的哈希函数，我们可以仿照Java标准库中字符串hashcode的求法，例如“abc”的hashcode等于（'a'*31+‘b'）*31+'c’ = 96354。我们根据我们自己的哈希函数求出匹配字符串的hashcode，接着我们遍历我们的源字符串，一开始是“abcc”，我们求出它的hashcode，如果他的hashcode跟匹配字符串相同，则遍历字符串看每一位是否相同，如果不同，则遍历下一串字符串“bccb”，判断方法如上，当遍历到“ccba”位置时，跟匹配字符串一样，返回匹配字符串的位置。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <string>
#define PRIM_BASE 31
using namespace std;
/**
*计算hashcode的方法跟上面例子的方法一样
*最坏时间复杂度为O(n-m)*m
**/
int rolling_hashCode_Strstr(const string &source,const string &pattern){
    unsigned source_code = 0;
    unsigned pattern_code = 0;
    unsigned pow = 1;
    size_t n = source.length();
    size_t m = pattern.length();

    for (int i=0; i <m; i++) {
        source_code = source_code*PRIM_BASE+source[i];
        pattern_code = pattern_code*PRIM_BASE+pattern[i];
        pow = pow*PRIM_BASE;
    }
    if (source_code==pattern_code&&source.substr(0,m)==pattern) {
        return 0;
    }else{
        for (int i = (int)m; i<n; i++) {
            source_code = source_code*PRIM_BASE+source[i];
            source_code = source_code - pow*source[i-m];
            if (source_code==pattern_code&&source.substr(i-m+1,m)==pattern) {
                return i-(int)m+1;
            }
        }

    }
    return -1;
}



int main(int argc, const char * argv[]) {
    cout<<rolling_hashCode_Strstr("abcdjdbsuad", "djdb")<<endl;
    return 0;
}

Comments