首页 > 其他 > 详细

字符串[BZOJ3277]

时间:2020-03-04 23:12:09      阅读:68      评论:0      收藏:0      [点我收藏+]

对于字符串\(x\)\(y\),假设字符串\(y\)在字符串\(x\)中若干的匹配位置,我们用\((l_i,r_i)\)来表示。二元组代表\(x\)\(x_{l_i}\sim x_{r_i}\)的字符串和\(y_1\sim y_{len(y)}\) 完全一致。这些二元组根据第一关键字从小到大排序后形成一个序列,定义一个函数\(F(x,y)\)的值为该序列的非空连续序列的数量。以\(F(babbabbababbab,?babb)?=?6\)为例子,匹配的二元组序列为:
\((1,?4),?(4,?7),?(9,?12)\)

非空连续序列为
\((1,?4)\)
\((4,?7)\)
\((9,?12)\)
\((1,?4),?(4,?7)\)
\((4,?7),?(9,?12)\)
\((1,?4),?(4,?7),?(9,?12)\)

现在给你一个字符串\(s\),请求出\(F(s,x)\)的和,其中\(x\)\(s\)的全部子串。

【输入格式】
输入一个字符串\(s\)

【输出格式】
输出题目要求的\(F\)值。

题解

模板更模板

建好后缀自动机 我们把代表原串前缀的那几个节点称作关键节点(即建自动机的时候每次添加一个新字符得到的那个新节点)

那么对于一个子串\(t\),我们把\(t\)在后缀自动机中所在的节点称作\(x\),在parent树中,\(x\)为根的子树中的 关键节点的数量 就是\(t\)在原串中出现的次数 把它记为\(cnt[x]\)

这个从每个关键节点开始暴力向上跳father 沿路数量++ 就能统计出来

然后这个“非空连续序列数量”其实就是\(\frac{a(a+1)}{2}\)

然后自动机中每个节点\(x\)含有的原串的子串数量就是\(len[x]-len[fa[x]]\)

那每个节点的答案就是\(cnt[x]*(cnt[x]+1)/2*(len[x]-len[fa[x]])\) 把所有节点的答案加起来就可以了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, key[100005];
char s[100005];
ll ans;

struct SAM{
    struct node{
        ll nxt[30], link, len, cnt;
    } tr[2000010]; 
    ll tot, lst;
    
    inline void init() {
        tot = lst = 0;
        tr[0].link = -1; tr[0].len = 0;
    }
    
    inline void build(char *str, ll len) {
        init();
        for (ll i = 1; i <= len; i++) {
            ll ind = ++tot, c = str[i] - 'a';
            tr[ind].len = tr[lst].len + 1;
            ll p = lst;
            while (p != -1 && !tr[p].nxt[c]) {
                tr[p].nxt[c] = ind;
                p = tr[p].link;
            }
            if (p == -1) {
                tr[ind].link = 0;
            } else {
                ll q = tr[p].nxt[c];
                if (tr[p].len + 1 == tr[q].len) {
                    tr[ind].link = q;
                } else {
                    ll clone = ++tot;
                    tr[clone].len = tr[p].len + 1;
                    tr[clone].link = tr[q].link;
                    for (ll j = 0; j < 26; j++) tr[clone].nxt[j] = tr[q].nxt[j];
                    while (p != -1 && tr[p].nxt[c] == q) {
                        tr[p].nxt[c] = clone;
                        p = tr[p].link;
                    }
                    tr[q].link = tr[ind].link = clone;
                }
            }
            lst = ind;
            key[i] = ind; //ind是一个关键节点
        }
    }
    
    inline void getans() {
        for (int i = 1; i <= n; i++) {
            int p = key[i];
            while (p != -1) {
                tr[p].cnt++;
                p = tr[p].link;
            }
        }
        for (ll i = 1; i <= tot; i++) {
            ll x = tr[i].len - tr[tr[i].link].len, y = tr[i].cnt;
            ans += y * (y + 1) / 2 * x;
        }
    }
}T;


int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    T.build(s, n);
    T.getans();
    printf("%lld\n", ans);
    return 0;
}

字符串[BZOJ3277]

原文:https://www.cnblogs.com/ak-dream/p/AK_DREAM45.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!