【BZOJ4566】[HAOI2016]找相同字符

题面

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。
其中\(1\leq|s1|,|s2|\leq n\)

题解

其实和这题差不多。
根据后缀数组常用套路，将将\(s1,s2\)用一个未曾出现的字符连起来
和上面那题一样的方法
算出来一个答案
然后减去分别左右两字符串选的贡献就好啦
代码

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
using namespace std; 
const int MAX_N = 4e5 + 5; 
int N; char a[MAX_N], b[MAX_N], c[MAX_N];
int sa[MAX_N], rnk[MAX_N], lcp[MAX_N]; 
void GetSA() { 
#define cmp(i, j, k) (y[i] == y[j] && y[i + k] == y[j + k]) 
    static int x[MAX_N], y[MAX_N], bln[MAX_N]; 
    int M = 122;
    for (int i = 0; i <= M; i++) bln[i] = 0; 
    for (int i = 1; i <= N; i++) bln[x[i] = a[i]]++; 
    for (int i = 1; i <= M; i++) bln[i] += bln[i - 1]; 
    for (int i = N; i >= 1; i--) sa[bln[x[i]]--] = i; 
    for (int k = 1; k <= N; k <<= 1) {
        int p = 0; 
        for (int i = 0; i <= M; i++) y[i] = 0;
        for (int i = N - k + 1; i <= N; i++) y[++p] = i; 
        for (int i = 1; i <= N; i++) if (sa[i] > k) y[++p] = sa[i] - k; 
        for (int i = 0; i <= M; i++) bln[i] = 0; 
        for (int i = 1; i <= N; i++) bln[x[y[i]]]++; 
        for (int i = 1; i <= M; i++) bln[i] += bln[i - 1]; 
        for (int i = N; i >= 1; i--) sa[bln[x[y[i]]]--] = y[i]; 
        swap(x, y); x[sa[1]] = p = 1; 
        for (int i = 2; i <= N; i++) x[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p; 
        if (p >= N) break;
        M = p; 
    } 
} 
void GetLcp() { 
    for (int i = 1; i <= N; i++) rnk[sa[i]] = i; 
    for (int i = 1, j = 0; i <= N; i++) { 
        if (j) --j; 
        while (a[i + j] == a[sa[rnk[i] - 1] + j]) ++j; 
        lcp[rnk[i]] = j; 
    } 
}
typedef long long ll; 
int lp[MAX_N], rp[MAX_N], stk[MAX_N], top; 
ll solve() { 
    GetSA(), GetLcp(); 
    top = 0, stk[0] = 1; 
    for (int i = 2; i <= N; i++) { 
        while (top > 0 && lcp[stk[top]] >= lcp[i]) --top; 
        lp[i] = i - stk[top], stk[++top] = i; 
    } 
    top = 0, stk[0] = N + 1;
    for (int i = N; i >= 2; i--) { 
        while (top > 0 && lcp[stk[top]] > lcp[i]) --top; 
        rp[i] = stk[top] - i, stk[++top] = i; 
    }
    ll res = 0; 
    for (int i = 2; i <= N; i++) res += 1ll * lp[i] * rp[i] * lcp[i]; 
    return res; 
} 
int main () { 
    ll ans = 0; int n, m; 
    scanf("%s", b + 1); scanf("%s", c + 1); 
    n = strlen(b + 1); m = strlen(c + 1); 
    N = n; for (int i = 1; i <= N; i++) a[i] = b[i]; 
    ans -= solve();
    N = m; for (int i = 1; i <= N; i++) a[i] = c[i]; 
    ans -= solve();
    N = n + m + 1; 
    for (int i = 1; i <= n; i++) a[i] = b[i];
    a[n + 1] = '#'; 
    for (int i = 1; i <= m; i++) a[i + n + 1] = c[i];
    ans += solve();
    printf("%lld\n", ans); 
    return 0; 
} 

【BZOJ4566】[HAOI2016]找相同字符

原文：https://www.cnblogs.com/heyujun/p/10305863.html