P3181 [HAOI2016]找相同字符

考虑如果是一个串中选出两个子串相同的方案数，可以得到height数组后用单调栈解决。那么考虑将两个串连在一起，中间以一个特殊字符间隔开，求答案。可以发现，重复计算了同时在一个串的答案，减去即可。

查看代码

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 8e5 + 10;
char s[N];
int top, stk[N];
int n, m, sa[N], rnk[N], ht[N], x[N], y[N], c[N];
void bucsort ()
{
    for (int i = 1; i <= m; ++i) c[i] = 0;
    for (int i = 1; i <= n; ++i) ++c[x[i]];
    for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i; --i) sa[c[x[y[i]]]--] = y[i];
}
void init ()
{
    for (int i = 1; i <= n; ++i)
        x[i] = s[i] - 'a' + 1, y[i] = i, sa[i] = 0;
    bucsort();
    for (int k = 1; k <= n; k <<= 1)
    {
        int cnt = 0;
        for (int i = n - k + 1; i <= n; ++i) y[++cnt] = i;
        for (int i = 1; i <= n; ++i)
            if (sa[i] > k) y[++cnt] = sa[i] - k;
        bucsort();
        for (int i = 1; i <= n; ++i) y[i] = x[i];
        x[sa[1]] = cnt = 1;
        for (int i = 2; i <= n; ++i)
            x[sa[i]] = cnt += (y[sa[i]] ^ y[sa[i - 1]] || y[sa[i] + k] ^ y[sa[i - 1] + k]);
        if ((m = cnt) == n) break;
    }
    for (int i = 1; i <= n; ++i) rnk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; ++i)
    {
        int j = sa[rnk[i] - 1];
        if (k) --k;
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
        ht[rnk[i]] = k;
    }
}
LL calc (string str)
{
    n = str.size(), m = 27;
    for (int i = 0; i < n; ++i) s[i + 1] = str[i];
    init();
    stk[0] = 1;
    LL res = 0;
    for (int i = 2; i <= n; ++i)
    {
        for (; top && ht[stk[top]] >= ht[i]; --top)
            res += (LL)ht[stk[top]] * (i - stk[top]) * (stk[top] - stk[top - 1]);
        stk[++top] = i;
    }
    for (; top; --top)
        res += (LL)ht[stk[top]] * (n + 1 - stk[top]) * (stk[top] - stk[top - 1]);
    return res;
}
int main ()
{
    string a, b;
    cin >> a >> b;
    cout << calc(a + (char)('z' + 1) + b) - calc(a) - calc(b);
    return 0;
}