HASH概述
Hash其实是一种散列技术，散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每一个关键字都对应一个存储位置。即：存储位置=f（关键字）。这样，在查找的过程中，只需要通过这个对应关系f 找到给定值key的映射f（key）。只要集合中存在关键字和key相等的记录，则必在存储位置f（key）处。我们把这种对应关系f 称为散列函数或哈希函数。
哈希冲突
在理想的情况下，每一个 关键字，通过哈希函数计算出来的地址都是不一样的。但是在实际情况中，我们常常会碰到两个关键字key1≠key2,但是f(key1) = f(key2), 这种现象称为冲突，并把key1和key2称为这个散列函数的同义词。
例题
给出a,b,c,d,e问:.a^b +c^d 是否等于 e
. —1e9 ≤a,b,c, d,e ≤ 1e9
#include <bits/stdc++.h> using namespace std; const long long mod=1e9+1e5+1e4+11; //取质数，尽可能取大，防止哈希冲突，取的方式可以研究一下 typedef long long ll; ll qpow(ll a,ll b){ ll res=1; while(b){ if(b&1){ res*=a; res%=mod; } b>>=1; a*=a; a%=mod; } return res; } //注意 在使用 函数后，得到的值可能是负的 //采用 ans=qpow,ans=(ans+mod)%mod,的方式得到正的 void solve(){ ll a,b,c,d,e; scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e); ll ans=0; ans+=qpow(a,b); ans%=mod; ans=(ans+mod)%mod; ans+=qpow(c,d); ans%=mod; ans=(ans+mod)%mod; e=(e+mod)%mod; if(ans==e) puts("AC!"); else puts("wrong"); } int main() { int t=1; while(t--){ solve(); } }
树哈希
字符串Hash
Hash[r]=s[1]*pr+s[2]*pr-1…s[r]*p0
Hash[l-1]=s[1]*pl-1+s[2]*pl-2…s[l-1]*p0
Hash[l~r]=s[l]*pr-l+s[l+1]*pr-l-1…s[r]*p0
void get_hash(){ return ((hash[r]-hash[l-1]*pow(p,r-l+1))%mod+mod)%mod; } 双哈希
例题
Your task is, given an integer N, to make a palidrome (word that reads the same when you reverse it) of length at least N. Any palindrome will do. Easy, isn’t it? That’s what you thought before you passed it on to your inexperienced team-mate. When the contest is almost over, you find out that that problem still isn’t solved. The problem with the code is that the strings generated are often not palindromic. There’s not enough time to start again from scratch or to debug his messy code. Seeing that the situation is desperate, you decide to simply write some additional code that takes the output and adds just enough extra characters to it to make it a palindrome and hope for the best. Your solution should take as its input a string and produce the smallest palindrome that can be formed by adding zero or more characters at its end.
Input Input will consist of several lines ending in EOF. Each line will contain a non-empty string made up of upper case and lower case English letters (‘A’-‘Z’ and ‘a’-‘z’). The length of the string will be less than or equal to 100,000.
Output For each line of input, output will consist of exactly one line. It should contain the palindrome formed by adding the fewest number of extra letters to the end of the corresponding input string.
Sample Input
aaaa
abba
amanaplanacanal
xyz
Sample Output
aaaa
abba
amanaplanacanalpanama
xyzyx
#include <bits/stdc++.h>
using namespace std;
const long long maxn=1e6+11;
const long long mod=1e9+1e5+1e4+11; //取质数，尽可能取大，防止哈希冲突，取的方式可以研究一下
typedef long long ll;
typedef unsigned long long ull;
unsigned long long h[maxn],po[maxn],h_f[maxn],p=131;//一个是哈希的数组，另一个是p次方的数组，还有一个反哈希数组,预存储,还有一个质数;
char s[maxn];
ull get_ha(int l,int r){
return h[r]-h[l-1]*po[r-l+1];
}
ull get_ha2(int l,int r){
return h_f[r]-h_f[l-1]*po[r-l+1];
}
//注意 在使用 函数后，得到的值可能是负的
//采用 ans=qpow,ans=(ans+mod)%mod,的方式得到正的
void solve(){
int len=strlen(s+1);
po[0]=1,h[0]=0;
for(int i=1;i<maxn;i++) po[i]=po[i-1]*p;
for(int i=1;i<=len;i++){
h[i]=h[i-1]*p+s[i];
h_f[i]=h_f[i-1]*p+s[len-i+1];
}
int minlen=0;//保留的字符量
for(int i=1;i<=len;i++)
{ //abbb,bbba是否相等?
//枚举i~len==1~len-i+1
ull pre=get_ha(i,len);
ull suf=get_ha2(1,len-i+1);
if(pre==suf){
minlen=i-1;
break;
}}
printf("%s",s+1);
for(int i=minlen;i>=1;i--){
printf("%c",s[i]);
}
puts("");
}
int main()
{
int t=1;
while(~scanf("%s",s+1)){
solve();
}
return 0;
}
原文：https://www.cnblogs.com/BlogBaudelaire/p/14345469.html