自动搬运

查看原文

来自洛谷，原作者为

	syksykCCC 相信并抓住那些源于热爱，忠于自我的每一个可能性

搬运于2025-08-24 22:30:09，当前版本为作者最后更新于2021-03-27 17:10:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大概是目前题解区最短的了。

因为 $s$ 串选择的是子序列，$t$ 串选择的是子串，所以显然 $t$ 的限制更严格，考虑枚举 $t$ 的子串 $t[i, j]$。

固定 $i$ 不动，$j$ 往后移动的时候，同时维护一个指针 $p$ 贪心的从前往后扫描 $s$ 串看是否还存在相同子序列。如果存在，把当前 $t[i, j]$ 的哈希值（一个 long long 大模数就行了）存到一个数组 $res$ 中。

枚举完了以后，把 $res$ 数组排序、去重，输出不一样的元素个数就行了。

时间复杂度其实也是 $O(n^2 \log n)$ 的。

#include <bits/stdc++.h>
using namespace std;
const int N = 3005, BASE = 51971;
const long long M = 2005091020050911;
int n;
char a[N], b[N];
long long t[N * N];
int main()
{
	scanf("%d %s %s", &n, a + 1, b + 1);
	for(int i = 1; i <= n; i++)
	{
		long long v = 0; int p = 1;
		for(int j = i; j <= n; j++)
		{
			while(p <= n && a[p] != b[j]) p++;
			if(p > n) break;
			p++;
			v = (1LL * v * BASE + b[j] - 'a' + 1) % M;
			t[++t[0]] = v;
		}
	}
	sort(t + 1, t + t[0] + 1);
	printf("%d\n", unique(t + 1, t + t[0] + 1) - t - 1);
	return 0;
}