CF427D. Match & Catch 后缀数组 计数

题目思路

要求求两个字符串的最短公共子串，且子串仅出现一次。

考虑将$s$和$t$进行拼接，中间用一个字符隔开，那么就可以对新串求得后缀数组$sa[i]$表示排名为$i$的后缀。那么就可以从小到大遍历整个后缀数组，然后求解。

首先考虑对于$sa[i]$和$sa[i-1]$，需要判断合法性：

• $sa[i]\in [1,n]\wedge sa[i-1]\in [n+2,n+1+m]$
• $sa[i-1]\in [1,n]\wedge sa[i]\in [n+2,n+1+m]$

然后考虑如何判断出现次数：这时$height$数组就有用了，$height[i]$表示$LCP(sa[i],sa[i-1])$，因此有：

$$LCP(sa[i],sa[i-1)>LCP(sa[i-1],sa[i-2])\wedge LCP(sa[i],sa[i-1])>LCP(sa[i],sa[i+1])$$
即为：
$$height[i]>height[i-1]\wedge height[i]>height[i+1]$$
那么满足上述两个条件时更新答案即可，当前答案即为：

$$max(height[i-1],height[i+1])+1$$

Code

#include 
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10;

namespace SA {
    int sa[N], tax[N], pool1[N], pool2[N], height[N];
    int *rnk = pool1, *tp = pool2;
    void sort(int n, int m) {
        for(int i = 0; i <= m; i++) tax[i] = 0;
        for(int i = 1; i <= n; i++) tax[rnk[i]]++;
        for(int i = 1; i <= m; i++) tax[i] += tax[i - 1];
        for(int i = n; i >= 1; i--) sa[tax[rnk[tp[i]]]--] = tp[i];
    }

    void build(string str, int n, int m) {
        for(int i = 1; i <= n; i++) rnk[i] = str[i] - '0' + 1, tp[i] = i;
        sort(n, m);
        for(int w = 1, p = 0; p < n; w <<= 1, m = p) {
            p = 0;
            for(int i = 1; i <= w; i++) tp[++p] = n - w + i;
            for(int i = 1; i <= n; i++) if(sa[i] > w) tp[++p] = sa[i] - w;
            sort(n, m);
            swap(tp, rnk);
            rnk[sa[1]] = p = 1;
            for(int i = 2; i <= n; i++) rnk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
        }
        int k = 0;
        for(int i = 1; i <= n; i++) {
            if(rnk[i] == 1) continue;
            if(k) --k;
            for(int j = sa[rnk[i] - 1]; str[i + k] == str[j + k]; ++k);
            height[rnk[i]] = k;
        } // Get the height array (height[i] = lcp(sa[i], sa[i - 1]))
    } 

    void reset() {
        memset(sa, 0, sizeof(sa));
        memset(rnk, 0, sizeof(pool1));
        memset(tp, 0, sizeof(pool2));
        memset(tax, 0, sizeof(tax));
        rnk = pool1, tp = pool2;
    }
}

using SA::sa;
using SA::rnk;
using SA::height;

inline void solve() {
    string s, t; cin >> s >> t;
    int n = s.size(), m = t.size(), len = n + 1 + m;
    SA::build('@' + s + '@' + t, len, 233);
    int minn = 1e17;
    auto judge = [&](int a, int b) {
        return (a >= 1 && a <= n && b >= n + 2 && b <= len);
    };
    for(int i = 1; i <= len; i++) {
        // cout << "???" << sa[i] << " -> " << height[i] << endl;
        if(judge(sa[i - 1], sa[i]) || judge(sa[i], sa[i - 1])) {
            // cout << "@@@" << height[i] << ", " << height[i - 1] << ", " << height[i + 1] << endl;
            if(height[i - 1] < height[i] && height[i] > height[i + 1]) {
                minn = min(minn, max(height[i - 1], height[i + 1]) + 1);
            }
        }
    }
    if(minn > 100000) minn = -1;
    cout << minn << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78