题解 P2957 真正的Hash

· · 题解

刚学完哈希，刷道水题练练手~~~

思路

1.先求两个字符串的前缀哈希值

2.枚举两个字符串的重复部分的长度

3.因为题目说“两个字符串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串”，所以只要判断两种情况：（划重点了）

one

第一个字符串的前缀的区间哈希值

和

第二个字符串的后缀的区间哈希值

two

第一个字符串的后缀的区间哈希值

和

第二个字符串的前缀的区间哈希值

比较一下，取最大值就完了

废话不多说，看就完了

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cmath>

using namespace std;
const int N=110,base=131;
typedef unsigned long long ULL;
ULL p[N],hl[N],hr[N];
char stra[N],strb[N];
int lena,lenb,lmax;

ULL get(ULL h[],int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}//求l~r的区间哈希值
int main()
{
    int i,j,res=INT_MIN;
    scanf("%s%s",stra+1,strb+1);
    lena=strlen(stra+1);
    lenb=strlen(strb+1);
    lmax=max(lena,lenb);//求最长字符串的长度
    p[0]=1;

    for(i=1;i<=lena;i++) hl[i]=hl[i-1]*base+(stra[i]-96);
    for(i=1;i<=lenb;i++) hr[i]=hr[i-1]*base+(strb[i]-96);
    for(i=1;i<=lmax;i++) p[i]=p[i-1]*base;
    //求前缀哈希值

    for(i=1;i<=lmax;i++)
    {
        int al,bl;
        if(lena<i||lenb<i) break;//判断边界
        al=get(hl,1,i)!=get(hr,lenb-i+1,lenb)?INT_MIN:i;
        //判断第一个字符串的前缀的区间哈希值和第二个字符串的后缀的区间哈希值是否相等
        bl=get(hl,lena-i+1,lena)!=get(hr,1,i)?INT_MIN:i;
        //判断第一个字符串的后缀的区间哈希值和第二个字符串的前缀的区间哈希值是否相等
        res=max(res,max(al,bl));//求最大值
    }
    printf("%d\n",res);
    return 0;//华丽的结尾~~~
}

本蒟蒻的第一篇题解，请多多支持