hash函数构建

• 采取26进制

  对于字符串str，令**H[i] = H[i-1]*26 + index(str[i]) **,最后H[i-1]就是str的hash值

  问题：hash值过大，无法表式

• 取模

  在上述基础上取模：H[i] = （H[i-1]*26 + index(str[i])）%mod

  问题：丧失了一定的唯一性

• 权衡：一个冲突概率极小的hash函数

  H[i] = （H[i-1]*p + index(str[i])）%mod

  其中p=10⁷ 数量级的素数(10000019)，mod=10⁹ 数量级的素数(1000000007)

例1：判断不同的字符串个数

问题描述

给出N个只有小写字母的字符串，判断其中不同的字符串的个数

代码实现

#include
#include
#include
#include
using namespace std;
const int MOD = 1000000007;
const int P = 10000019;
vector ans;
//字符串hash
long long hashFunc(string str){
    long long H = 0;
    for(int i = 0; i < str.length(); i++){
        H = (H*P + str[i] - 'a') % MOD;
    }
    return H;
}
int main(){
    string str;
    while(getline(cin, str), str != "#"){
        long long id = hashFunc(str);
        ans.push_back(id);
    } 
    sort(ans.begin(), ans.end());
    int count = 0;
    for(int i = 0; i < ans.size(); i++){
        if(i == 0 || ans[i] != ans[i-1])
            count++;
    }
    cout<< count << endl;
    return 0;
}

例2： 最长公共子串

前置：求解子串str[i…j]的hash值H[i…j]

符号含义：

• H[i..j] : str[i]~str[j]这一子串对应的hash值，即该子串对应的p进制数
• H[i] : H[0…i]

H[i…j] = index(str[i]) * p^j-i + index(str[i-1]) * p^j-i-1 + … + index(str[j]) * p⁰

H[i] = H[i-1] * p + index(str[i])

于是 ：

所以：

H[i…j] = H[j] - H[i - 1] * p^j-i+1求完str的H数组后，直接调取下标j 和 i-1 即可求得

取模：

H[i…j] = （H[j] - H[i - 1] * p^j-i+1）%mod

非负处理：（括号内可能为负值）加模再取模

H[i…j] = （（H[j] - H[i - 1] * p^j-i+1）%mod + mod）%mod

步骤

1. 计算H[]数组
2. 求出两个字符串所有子串的hash值以及对应的长度
3. 子串两两比较，得出长度最大值

代码

#include
#include
#include
#include
#include