题解 P7469 【[NOI Online 2021 提高组] 积木小赛】

syksykCCC · 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;
}