LOJ2823 三个朋友 ——查询字串的哈希值

概念

查询字串的hash值

我们所说的哈希通常都是进制哈希，因为它具有一些很方便的性质，例如，具有和前缀和类似的性质。

假设一个字符串的前缀哈希值记为 $h[i]$，进制为 $base$，那么显然 $h[i] = h[i-1] imes 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 - 1] * p[r - l + 1];
}

其中，乘以 $p[r-l+1]$ 相当于左移了 $r-l+1$ 位。

同样，我们可以 $O(1)$ 得到字串中删除一个字符后的hash值。

ull get_s(int l, int r, int x) {
    return get_hash(l, x - 1) * p[r - x] + get_hash(x + 1, 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 = 233;
const int maxn = 2000000+10;
ull h[maxn], p[maxn];
char s[maxn];
int len;

void init()
{
    ll ans = 0;
    for(int i=0;i<len;i++)
    {
        ans = (ans*base) + (ull)s[i];
        h[i] = ans;
    }
    p[0] = 1;
    for(int i=1;i<=len;i++)
    {
        p[i] = p[i-1]*base;
    }
}

inline ll gethash(int l,int r)
{
    return h[r] - h[l-1]*p[r-l+1];
}

inline ll del(int l,int r,int x)
{
    if(x<l||x>r)
        return gethash(l,r);
    return gethash(l,x-1)*p[r-x]+gethash(x+1,r);
}

inline int check(int x) //检查去掉第x位时是否合法
{
    if(x<=len/2&&del(0,len-1,x)==del(0,len>>1,x)*p[len>>1]+del(0,len>>1,x))
        return 1;
    else if(x>len/2&&del(0,len-1,x)==del(0,(len>>1)-1,x)*p[len>>1]+del(0,(len>>1)-1,x))
        return 1;
    else
        return 0;
}

int main()
{
    scanf("%d",&len);
    scanf("%s",s);
    init();
    int cnt = 0;
    int ii = -1;
    ll num;
    for(int i=0;i<len;i++)
    {
        if(check(i))
        {
            cnt++;
            if(ii==-1)
            {
                ii=i;
                num = del(0,len-1,i);
            }
            else
            {
                if(del(0,len-1,ii)==del(0,len-1,i))  //可能是相同的串
                    cnt--;
            }
        }
        if(cnt==2)
        {
            printf("NOT UNIQUE
");
            return 0;
        }
    }
    if(cnt==1)
    {
        int m = 0;
        for(int j=0;j<len;j++)   //输出结果
        {
            if(j==ii)
                continue;
            printf("%c",s[j]);
            m++;
            if(m==(len-1)/2)
                break;
        }
        printf("
");
    }
    if(cnt==0)
    {
        printf("NOT POSSIBLE
");
    }
    return 0;
}

参考链接：https://loj.ac/submission/576434