hdu6068 Classic Quotation-哈希

传送门

题意:

给定一个长度为$n$的串$s$,一个长度为$m$的串$t$。
有k次询问,每次给定$l,r$,在$[1,l]$中随机一个整数$i$,在$[r,n]$中随机一个整数$j$,问$t$在$s[1…i]+s[j…n]$中的出现次数。
$n,k\leq100000,m\leq100$

Solution:

答案可以分成三部分

  1. $t$包含在$s[1…i]$内
  2. $t$包含在$s[j…n]$内
  3. $t$的前缀在$s[1…i]$内,$t$的后缀在$s[j…n]$内
    1和2都很好处理,3看起来不是很好处理,其实很简单:枚举前缀长度$k$,$pre[i][j]$表示前缀在s串的结尾为$i$,前缀长度为$j$是否能匹配,后缀操作类似,最后求一遍前缀和即可,至于1和2的情况,则可以用$L[i]$表示在$s$串的结尾为$i$是否能匹配到t串,然后求两遍前缀和(一遍求出前$i$位有多少个$t$串,再一遍求出前缀和),注意计数的细节。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50010;
int mi[N],ha[N],hb[N],ha2[N],hb2[N],mi2[N];
char a[N],b[N];
const int bas=211;
const int mod=1315326179;
const int mod2=1e9+7;
int T,n,m,q,l,r;
int nl[N],nr[N];
int pre[N][110],suf[N][110];
int geta(int l,int r)
{
return (1ll*ha[r]-(1ll*ha[l-1]*mi[r-l+1])%mod+mod)%mod;
}
int getb(int l,int r)
{
return (1ll*hb[r]-(1ll*hb[l-1]*mi[r-l+1])%mod+mod)%mod;
}
int geta2(int l,int r)
{
return (1ll*ha2[r]-(1ll*ha2[l-1]*mi2[r-l+1])%mod2+mod2)%mod2;
}
int getb2(int l,int r)
{
return (1ll*hb2[r]-(1ll*hb2[l-1]*mi2[r-l+1])%mod2+mod2)%mod2;
}
void getha()
{
for (int i=1;i<=n;i++) ha[i]=(1ll*ha[i-1]*bas+a[i])%mod;
for (int i=1;i<=m;i++) hb[i]=(1ll*hb[i-1]*bas+b[i])%mod;
for (int i=1;i<=n;i++) ha2[i]=(1ll*ha2[i-1]*bas+a[i])%mod2;
for (int i=1;i<=m;i++) hb2[i]=(1ll*hb2[i-1]*bas+b[i])%mod2;
}
int main()
{
mi[0]=1;mi2[0]=1;
for (int i=1;i<=N-10;i++) mi[i]=(1ll*mi[i-1]*bas)%mod,mi2[i]=(1ll*mi2[i-1]*bas)%mod2;
scanf("%d",&T);
while (T--)
{
memset(suf,0,sizeof(suf));
memset(pre,0,sizeof(pre));
scanf("%d%d%d",&n,&m,&q);
scanf("%s",a+1);scanf("%s",b+1);
getha();
for (int i=1;i<=n;i++)
for (int j=1,ed=min(m,i);j<=ed;j++)
pre[i][j]=(geta(i-j+1,i)==getb(1,j)&&geta2(i-j+1,i)==getb2(1,j));
reverse(a+1,a+1+n);reverse(b+1,b+1+m);
getha();
for (int i=1;i<=n;i++)
for (int j=1,ed=min(m,i);j<=ed;j++)
suf[i][j]=(geta(i-j+1,i)==getb(1,j)&&geta2(i-j+1,i)==getb2(1,j));
int cnt=0;
for (int i=1;i<=n;i++)
cnt+=pre[i][m],nl[i]=nl[i-1]+cnt;
cnt=0;
for (int i=1;i<=n;i++)
cnt+=suf[i][m],nr[i]=nr[i-1]+cnt;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
pre[i][j]+=pre[i-1][j],suf[i][j]+=suf[i-1][j];
for (int i=1;i<=q;i++)
{
long long ans=0;
scanf("%d%d",&l,&r);
r=n-r+1;
ans+=1ll*nl[l]*r+1ll*nr[r]*l;
for (int i=1;i<m;i++)
ans+=1ll*pre[l][i]*suf[r][m-i];
printf("%lld\n",ans);
}
}
}
作者

Fizzmy

发布于

2018-01-07

更新于

2021-08-06

许可协议

评论