[bzoj3238][Ahoi2013]差异——后缀自动机

时间:2020-12-12 00:59:53

Brief Description

[bzoj3238][Ahoi2013]差异——后缀自动机

Algorithm Design

下面给出后缀自动机的一个性质:

两个子串的最长公共后缀,位于这两个串对应的状态在parent树上的lca状态上。并且最长公共后缀的长度就是lca状态的len。

证明:对于一个串,他的所有祖先节点都是他的后缀,并且深度越大,长度越长,由此不难说明两个子串的最长公共后缀一定在lca状态上。考察这个lca,他代表的所有子串一定都是两个子串的公共后缀,我们直接取最大的就可以了。

有了这个性质,我们就可以开始乱搞了。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
const ll maxn = 500100 << 1;
char s[maxn], str[maxn];
ll head[maxn], f[maxn];
ll ans;
ll n, cnt = 1;
struct edge {
ll to, next;
} e[maxn];
void add_edge(ll u, ll v) {
e[++cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
struct Suffix_Automaton {
ll fa[maxn], trans[maxn][26], len[maxn], right[maxn];
ll last, root, sz;
bool flag[maxn];
void init() {
memset(flag, 0, sizeof(flag));
sz = 0;
last = root = ++sz;
}
void insert(ll x) {
ll p = last, np = last = ++sz;
len[np] = len[p] + 1;
flag[np] = 1;
right[np] = right[p] + 1;
for (; !trans[p][x]; p = fa[p])
trans[p][x] = np;
if (p == 0)
fa[np] = root;
else {
ll q = trans[p][x];
if (len[q] == len[p] + 1) {
fa[np] = q;
} else {
ll nq = ++sz;
fa[nq] = fa[q];
memcpy(trans[nq], trans[q], sizeof(trans[q]));
len[nq] = len[p] + 1;
fa[q] = fa[np] = nq;
for (; trans[p][x] == q; p = fa[p])
trans[p][x] = nq;
}
}
}
void pre() {
for (ll i = 1; i <= sz; i++) {
if (fa[i])
add_edge(fa[i], i);
}
}
void print() {
for (ll i = 1; i <= sz; i++) {
printf("%3lld ", i);
}
printf("\n");
for (ll i = 1; i <= sz; i++) {
printf("%3lld ", len[i]);
}
printf("\n");
for (ll i = 1; i <= sz; i++)
if (flag[i]) {
printf("%lld:", i);
for (ll j = 1; j <= len[i]; j++)
printf("%c", str[right[i] - (len[i] - j + 1) + 1]);
printf("\n");
}
printf("\n");
}
} sam;
void dfs(ll x) {
ll ct = 0;
f[x] = sam.flag[x] ? 1 : 0;
for (ll i = head[x]; i; i = e[i].next) {
dfs(e[i].to);
ans -= 1ll * 2 * (1ll * f[e[i].to] * ct) * (sam.len[x]);
ct += f[e[i].to];
}
if (f[x] == 1) {
ans -= 1ll * 2 * (1ll * ct) * (sam.len[x]);
}
f[x] += ct;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input", "r", stdin);
#endif
scanf("%s", s + 1);
n = strlen(s + 1);
sam.init();
for (ll i = 1; i <= n; i++) {
ans += (n * i) - i * i + ((n * n - i * i + n - i) >> 1);
str[i] = s[n - i + 1];
}
for (ll i = 1; i <= n; i++)
sam.insert(str[i] - 'a');
sam.pre();
// sam.print();
// printf("%lld\n", ans);
dfs(sam.root);
printf("%lld\n", ans);
}

[bzoj3238][Ahoi2013]差异——后缀自动机的更多相关文章

  1. BZOJ3238&colon; &lbrack;Ahoi2013&rsqb;差异&lpar;后缀自动机&rpar;

    题意 题目链接 Sol 前面的可以直接算 然后原串翻转过来,这时候变成了求任意两个前缀的最长公共后缀,显然这个值应该是\(len[lca]\),求出\(siz\)乱搞一下 #include<bi ...

  2. BZOJ 3238&colon; &lbrack;Ahoi2013&rsqb;差异 &lbrack;后缀自动机&rsqb;

    3238: [Ahoi2013]差异 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 2512  Solved: 1140[Submit][Status ...

  3. bzoj3238 &lbrack;Ahoi2013&rsqb;差异 后缀数组&plus;单调栈

    [bzoj3238][Ahoi2013]差异 Description Input 一行,一个字符串S Output 一行,一个整数,表示所求值 Sample Input cacao Sample Ou ...

  4. &lbrack;Ahoi2013&rsqb;差异&lpar;后缀自动机&rpar;

    /* 前面的那一坨是可以O1计算的 后面那个显然后缀数组单调栈比较好写??? 两个后缀的lcp长度相当于他们在后缀树上的lca的深度 那么我们就能够反向用后缀自动机构造出后缀树然后统计每个点作为lca ...

  5. 洛谷P4248 &lbrack;AHOI2013&rsqb;差异&lpar;后缀自动机求lcp之和&rpar;

    题目见此 题解:首先所有后缀都在最后一个np节点,然后他们都是从1号点出发沿一些字符边到达这个点的,所以下文称1号点为根节点,我们思考一下什么时候会产生lcp,显然是当他们从根节点开始一直跳相同节点的 ...

  6. BZOJ 3238 &lbrack;Ahoi2013&rsqb;差异 ——后缀自动机

    后缀自动机的parent树就是反串的后缀树. 所以只需要反向构建出后缀树,就可以乱搞了. #include <cstdio> #include <cstring> #inclu ...

  7. &lbrack;AHOI2013&rsqb;差异 后缀自动机&lowbar;Parent树

    题中要求: $\sum_{1\leqslant i < j \leq n } Len(T_{i}) +Len(T_{j})-2LCP(T_{i},T_{j})$ 公式左边的部分很好求,是一个常量 ...

  8. BZOJ&period;3238&period;&lbrack;AHOI2013&rsqb;差异&lpar;后缀自动机 树形DP&sol;后缀数组 单调栈&rpar;

    题目链接 \(Description\) \(Solution\) len(Ti)+len(Tj)可以直接算出来,每个小于n的长度会被计算n-1次. \[\sum_{i=1}^n\sum_{j=i+1 ...

  9. BZOJ 3238&colon; &lbrack;Ahoi2013&rsqb;差异 后缀自动机 树形dp

    http://www.lydsy.com/JudgeOnline/problem.php?id=3238 就算是全局变量,也不要忘记,初始化(吐血). 长得一副lca样,没想到是个树形dp(小丫头还有 ...

随机推荐

  1. 我与ADO&period;NET二三事&lpar;2&rpar;

    继上篇开始,这里主要再次精简.因为大家已经熟悉了主要思想以及它的工作方式.那么这里提供的案例改动会很大.上篇的DatabaseCommand***均是为了大家能够轻松的理解所临时编写的.这次提供的接口 ...

  2. docker on Mac

    贡献一篇: 云主机可以选择操作系统镜像快速创建主机,这比虚拟机更便捷了,我们本地也可以这么做了,因为有了 Docker 这个东西.它依赖于 LXC(Linux Container),能从网络上获得配置 ...

  3. CI框架多目录设置

    1,设置目的,前台与后台实现独立目录管理 2.通过http://www.myci.com  访问前台,通过http://www.myci.com/admin 访问后台,   多目录的意思是指在同一个网 ...

  4. HTML5 Web存储&lpar;Web Storage&rpar;技术及用法

    在如今的Web开发中,HTML5是大家讨论的最大一个话题.HTML5提供的新功能特征使得Web程序员如虎添翼,并免去了以往钻研各种方法来让网站更好.更快.更灵活的气力.这些新功能中有一个非常让我感兴趣 ...

  5. BTrace &colon; Java 线上问题排查神器

    BTrace 是什么 BTrace 是检查和解决线上的问题的杀器,BTrace 可以通过编写脚本的方式,获取程序执行过程中的一切信息,并且,注意了,不用重启服务,是的,不用重启服务.写好脚本,直接用命 ...

  6. &lbrack;整理&rsqb;HTTPS和SSL证书

    在互联网安全通信方式上,目前用的最多的就是https配合ssl和数字证书来保证传输和认证安全了.本文追本溯源围绕这个模式谈一谈. 名词解释 首先解释一下上面的几个名词: • https:在http(超 ...

  7. 命名空间的using声明

    using声明具有如下的形式: using namespace::name; 一旦声明了上述语句,就可以直接访问命名空间中的名字: #include<iostream> //using声明 ...

  8. Android PopupWindow 仿微信弹出效果

    项目中,我须要PopupWindow的时候特别多,这个东西也特别的好使,所以我今天给大家写一款PopupWindow 仿微信弹出效果.这样大家直接拿到项目里就能够用了! 首先让我们先看效果: 那么我首 ...

  9. c&plus;&plus;获取随机数

    方法一: 使用 rand 函数可以获取,如下. 随机数大小是在0到RAND_MAX,值为2147483647,它是在stdlib中定义的,如果我们希望在某个范围内,可以使用 % 结合 / 来实现. 但 ...

  10. 3、CommonChunkPlugin提取公共js-以提取一个jquery为例

    cnpm install css-loader --save-dev    //css-loader 是将css打包进js cnpm install style-loader --save-dev   ...