题解 P7469 【[NOI Online 2021 提高组] 积木小赛】
Karry5307
·
·
题解
题意
给定两个长度为 n 的字符串 S 和 T，求 T 中有多少本质不同的子串是 S 的子序列。
### 题解
比较简单。
对 $S$ 建立子序列自动机，这样就可以串长复杂度的看一个串是否为 $S$ 的子序列了。
由于子序列自动机是可以一个一个加字符匹配，所以可以直接枚举左端点然后从左往右枚举右端点。
至于考虑本质不同的串的话就哈希一下就好了。
由于可以通过构造 $\texttt{ab}$ 串来使答案大小为 $3\times 10^6$ 量级，所以哈希时候模数要设的比较大。（~~我不会告诉你我随机构造 $\texttt{ab}$ 串卡掉了某位同学的双哈希~~）
然后为了常数需要手写哈希表，本机测 $n=3000$ 的 $\texttt{ab}$ 串的时候 map 4s 手写哈希 0.3s。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=9e6+51;
const li MOD1=8530716171517,MOD2=8530716771587;
struct HashTable{
const ll MOD=8530771;
ll tot;
ll last[MAXN],prev[MAXN/2];
li hsh1[MAXN/2],hsh2[MAXN/2];
inline void insert(li hv1,li hv2);
inline ll query(li hv1,li hv2);
};
HashTable hsh;
ll n,res,cur;
li hsh1,hsh2;
ll nxt[3051][27];
char s[3051],t[3051];
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
inline void HashTable::insert(li hv1,li hv2)
{
ll x=hv1%MOD;
prev[++tot]=last[x],hsh1[tot]=hv1,hsh2[tot]=hv2,last[x]=tot;
}
inline ll HashTable::query(li hv1,li hv2)
{
ll x=hv1%MOD;
for(register int i=last[x];i;i=prev[i])
{
if(hsh1[i]==hv1&&hsh2[i]==hv2)
{
return 1;
}
}
return 0;
}
int main()
{
n=read(),scanf("%s%s",s+1,t+1);
for(register int i=n;i;i--)
{
memcpy(nxt[i-1],nxt[i],sizeof(nxt[i])),nxt[i-1][s[i]-'a']=i;
}
for(register int i=1;i<=n;i++)
{
cur=hsh1=hsh2=0;
for(register int j=i;j<=n;j++)
{
if(!(cur=nxt[cur][t[j]-'a']))
{
break;
}
hsh1=(hsh1*131+t[j]-'a'+1)%MOD1,hsh2=(hsh2*131+t[j]-'a'+1)%MOD2;
!hsh.query(hsh1,hsh2)?hsh.insert(hsh1,hsh2),res++:1;
}
}
printf("%d\n",res);
}
```