题解 P7469【[NOI Online 2021 提高组] 积木小赛】
Hexarhy
2021-03-27 17:46:08
### Preface
唯一一道可做题。套路得不能再套路。
### Solution
枚举 $B$ 的子串的同时，我们可以将一个指针指向 $A$，同时进行子序列的匹配。$B$ 每枚举一位，$A$ 的指针就往后找匹配的。显然这个过程是 $O(n)$。
去重可以使用 hash，将所有匹配的字符串的 hash 值都存进数组里，最后 `sort` 和 `unique` 一下即可。
时间复杂度 $O(n^2\log n^2)$，需要较优秀的常数。
### Code
hash 选个大质数就好了（确信）。
**本代码 C++ 或者 C++11 & O2 可通过。**
```cpp
#include <cstdio>
#include <algorithm>
typedef unsigned long long ll;
const int MAXN=3002;
int n,cnt;
char a[MAXN],b[MAXN];
ll ans[MAXN*MAXN];
const ll base=2333,MOD=1e14+1;
int main()
{
scanf("%d%s%s",&n,a,b);
for(int i=0;i<n;++i)
{
ll res=1;
for(int j=i,k=0;k<n && j<n;++j,++k)
{
while(k<n && a[k]!=b[j]) ++k;
if(k>=n) break;
res=(res*base+b[j]-'a'+1)%MOD;
ans[++cnt]=res;
}
}
std::sort(ans+1,ans+1+cnt);
printf("%d\n",std::unique(ans+1,ans+1+cnt)-ans-1);
return 0;
}
```