最近在学习字符串的知识，在字符串上我跟大一的时候是没什么区别的，所以恶补了很多基础的算法，今天补了一下字符串哈希，看的是大一新生的课件学的，以前觉得字符串哈希无非就是跟普通的哈希没什么区别，倒也没觉得有什么特别大的用处，敲一敲才发现其实讲究还是比较多的。哈希冲突是常有的事，换一下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;
} |