url: https://www.luogu.com.cn/problem/P7469

tag:
NOI Online 2021 提高组，字符串，哈希

思路：
用双重循环枚举每一个b中的字串，对于每一个枚举的字串，扫描一遍a，找出a中相同的子序，然后计算哈希值并存储，最后遍历结束，对哈希数组去重得出答案。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010, BASE = 51971;
const long long M = 2005091020050911;
int n;
char a[N], b[N];
long long t[N * N];
int main()
{
    cin >> 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);
    cout << unique(t + 1, t + t[0] + 1) - t - 1;
    return 0;
}