最近在学习字符串的知识，在字符串上我跟大一的时候是没什么区别的，所以恶补了很多基础的算法，今天补了一下字符串哈希，看的是大一新生的课件学的，以前觉得字符串哈希无非就是跟普通的哈希没什么区别，倒也没觉得有什么特别大的用处，敲一敲才发现其实讲究还是比较多的。哈希冲突是常有的事，换一下mod，换一下进制数才有可能过，另外一种说法是用两个互质的量做hash，如果两个都相等的话那冲突就会少很多，这个倒没有做过多大的尝试，侥幸地过了一下这道题
|
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
42
43
44
45
46
47
48 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<string>#include<algorithm>#define maxn 50000#define mod 40157#define xx 133using
namespace
std;char
s[maxn + 50];char
t[maxn + 50];int
h1[maxn + 50];int
h2[maxn + 50];int
xpow[maxn+50];int
main(){ xpow[0] = 1; for
(int
i = 1; i <= maxn + 20; i++) xpow[i] = xpow[i - 1] * xx%mod; while
(~scanf("%s%s", s + 1,t + 1)) { h1[0] = h2[0] = 0; int
n = strlen(s+1), m = strlen(t+1); for
(int
i = 1; i <= n; i++) h1[i] = (h1[i - 1] * xx%mod + s[i])%mod; for
(int
i = 1; i <= m; i++) h2[i] = (h2[i - 1] * xx%mod + t[i])%mod; int
ans = 0; int
len = min(n, m); for
(int
i = 1; i <= len; i++){ int
lhs = (h1[i] - h1[0] * xpow[i] % mod + mod) % mod; int
rhs = (h2[m] - h2[m - i] * xpow[i]% mod + mod) % mod; if
(lhs == rhs) ans = i; } if
(!ans) puts("0"); else{ for
(int
i = 1; i <= ans; i++){ printf("%c", s[i]); } printf(" %d\n", ans); } } return
0;} |
HDU2594 Simpsons’ Hidden Talents 字符串哈希
原文：http://www.cnblogs.com/chanme/p/3538750.html