Magic FZU – 2280(字符串哈希)

题目链接

https://cn.vjudge.net/problem/FZU-2280

题目大意

n个字符串,每个字符串有自己的权值。
有两种操作,1是将第x个字符串的权值更改为y,2是查询权值小于等于第x个字符串的权值并且第x个字符串是它的后缀的字符串的个数。

解题思路

字符串哈希预处理,查询时暴力枚举查询。

字符串哈希

字符串哈希就是将字符串按照类似二进制数转10进制数的方式将字符串哈希为一个数值,这样两个字符串是否相等就可以用数值间的比较完成了。
而对于l – r区间的hash值,则为:
hash[r]-hash[l-1]*x^(r-l+1)

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed=131;
const int maxn=1e3+5;
const int mod=998244353;
ull p[maxn],ha[maxn][maxn];
char str[maxn][maxn];
int a[maxn],len[maxn];
int n,q;

void hashh(int id,char *s)
{
    ha[id][0]=0;
    for(int i=1;i<=len[id];i++)
    {
        ha[id][i]=ha[id][i-1]*seed+s[i];
    }
}

ull gethash(int id,int l,int r)
{
    return ha[id][r]-ha[id][l-1]*p[r-l+1];
}

int check(int mid)
{
    int ans=0;
    ull need=gethash(mid,1,len[mid]);
    for(int i=1;i<=n;i++)
    {
        if(a[i]>a[mid])continue;
        if(len[i]<len[mid])continue;
        ull now=gethash(i,len[i]-len[mid]+1,len[i]);
        if(now==need)
            ans++;
    }
    return ans;
}

int main()
{
    p[0]=1;
    for(int i=1;i<=1005;i++)
    {
        p[i]=p[i-1]*seed;
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int val;
            scanf("%s%d",str[i]+1,&val);
            len[i]=strlen(str[i]+1);
            hashh(i,str[i]);
            a[i]=val;
        }
        scanf("%d",&q);
        while(q--)
        {
            int op,x,y;
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d",&x,&y);
                a[x]=y;
            }
            else
            {
                scanf("%d",&x);
                int ans=check(x);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注