HDU – 5769 Substring 后缀自动机+二分、新增distinct子串的个数和位置

Substring 后缀自动机+二分

 Source

HDU - 5769

My Solution

题意：每次给出一个字母ch和一个字符串s，求s中有多少个不同的子串含有字母ch。

后缀自动机+二分、新增distinct子串的个数和位置

首先这里要用到后缀自动机的一个性质，

添加第i个字符时，自动机里新增了diff = val[np] - val[pre[np]] 个与原先不同的子串，它们分别是 s[0......i]，s[1......i]，……，s[diff-1......i]，

这里可以证明，当k < j < i 时，如果 s[j......i]是新增的不同子串，则s[k......i]包括了s[j......i] 故s[k......i]必定也是新增的不同子串，得证。

故每添加一个字符的时候，得到diff 为新增的不同子串，它们分别是 s[0......i]，s[1......i]，……，s[diff-1......i] ，

故二分的方法，找到尽可能大的add，sum[i+1] - sum[add-1] > 0，即子串里包含字符ch，找到最大的add之后，s[j......i]，0<=j<=add-1都是包含字符ch的新增不同子串。

复杂度 略大于 O(T*n), 远小于 O(T*n*logn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 2*1e5 + 8;

string s;
struct SAM{
    int ch[MAXN][26], pre[MAXN], val[MAXN];
    int last, tot;
    void init(){
        last = tot = 0;
        memset(ch[0], -1, sizeof ch[0]);
        pre[0] = -1; val[0] = 0;
    }
    int extend(int c){
        int p = last, np = ++tot;
        val[np] = val[p] + 1;
        memset(ch[np], -1, sizeof ch[np]);
        while(~p && ch[p][c] == -1) ch[p][c] = np, p = pre[p];
        if(p == -1) pre[np] = 0;
        else{
            int q = ch[p][c];
            if(val[q] != val[p] + 1){
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                val[nq] = val[p] + 1;
                pre[nq] = pre[q];
                pre[q] = pre[np] = nq;
                while(~p && ch[p][c] == q) ch[p][c] = nq, p = pre[p];
            }
            else pre[np] = q;
        }
        last = np;
        return val[np] - val[pre[np]];
    }
} sam;

int sum[MAXN];

int main()
{
    #ifdef LOCAL
    freopen("18.IN", "r", stdin);
    //freopen("18.out", "w", stdout);

    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int T, n, i, l, r, mid, kase = 1;
    LL ans, add;
    char ch;
    cin >> T;
    while(T--){
        cin >> ch >> s;
        n = s.size(); sum[0] = 0;
        for(i = 1; i <= n; i++){
            sum[i] = sum[i-1] + (s[i-1] == ch);
        }
        sam.init(); ans = 0;
        for(i = 0; i < n; i++){
            r = sam.extend(s[i] - 'a');
            l = 0, r += 1, add = 0;
            while(l + 1 < r){ mid = (l + r) >> 1;
                if(sum[i+1] - sum[mid-1] > 0){
                    add = l = mid;
                }
                else r = mid;
            }
            ans += add;
        }
        cout << "Case #" << kase << ": " << ans << "n"; kase++;
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx