概念
查询字串的hash值
我们所说的哈希通常都是进制哈希，因为它具有一些很方便的性质，例如，具有和前缀和类似的性质。
假设一个字符串的前缀哈希值记为 $h[i]$，进制为 $base$，那么显然 $h[i] = h[i-1] \times base + s[i]$.
记 $p[i]$ 为 $base$ 的 $i$ 次方，那么我们可以 $O(1)$ 得到一个字串的哈希值。
typedef unsigned long long ull;
ull get_hash(int l, int r) {
return h[r] - h[l - ] * p[r - l + ];
}
其中，乘以 $p[r-l+1]$ 相当于左移了 $r-l+1$ 位。
同样，我们可以 $O(1)$ 得到字串中删除一个字符后的hash值。
ull get_s(int l, int r, int x) {
return get_hash(l, x - ) * p[r - x] + get_hash(x + , r);
}例题
题意：给定一个字符串 $S$，先将字符串 $S$ 复制一次，得到字符串 $T$，然后在 $T$ 中插入一个字符，得到字符串 $U$。现给出字符串 $U$，要求重新构造出 $S$。
分析：
枚举每一个位置，剩下的应是两个相同的字符串，根据hash值判断一下。
#include<bits/stdc++.h>
using namespace std; typedef long long ll;
typedef unsigned long long ull;
const ull base = ;
const int maxn = +;
ull h[maxn], p[maxn];
char s[maxn];
int len; void init()
{
ll ans = ;
for(int i=;i<len;i++)
{
ans = (ans*base) + (ull)s[i];
h[i] = ans;
}
p[] = ;
for(int i=;i<=len;i++)
{
p[i] = p[i-]*base;
}
} inline ll gethash(int l,int r)
{
return h[r] - h[l-]*p[r-l+];
} inline ll del(int l,int r,int x)
{
if(x<l||x>r)
return gethash(l,r);
return gethash(l,x-)*p[r-x]+gethash(x+,r);
} inline int check(int x) //检查去掉第x位时是否合法
{
if(x<=len/&&del(,len-,x)==del(,len>>,x)*p[len>>]+del(,len>>,x))
return ;
else if(x>len/&&del(,len-,x)==del(,(len>>)-,x)*p[len>>]+del(,(len>>)-,x))
return ;
else
return ;
} int main()
{
scanf("%d",&len);
scanf("%s",s);
init();
int cnt = ;
int ii = -;
ll num;
for(int i=;i<len;i++)
{
if(check(i))
{
cnt++;
if(ii==-)
{
ii=i;
num = del(,len-,i);
}
else
{
if(del(,len-,ii)==del(,len-,i)) //可能是相同的串
cnt--;
}
}
if(cnt==)
{
printf("NOT UNIQUE\n");
return ;
}
}
if(cnt==)
{
int m = ;
for(int j=;j<len;j++) //输出结果
{
if(j==ii)
continue;
printf("%c",s[j]);
m++;
if(m==(len-)/)
break;
}
printf("\n");
}
if(cnt==)
{
printf("NOT POSSIBLE\n");
}
return ;
}