HIHOcoder 1466 后缀自动机六·重复旋律9
思路后缀数组+博弈论的好题，首先对两个串都建出SAM，然后题目的要求实际上就是在SAM的trans上转移即可DAG的博弈是经典问题，然后dfs求出SG函数，两个游戏的组合就是把SG函数异或起来，异或是0就是先手必败，不是0就是先手必胜然后要求先手必胜，所以就是求异或不为0接下来递推的求出第k大的串即...
ACdream 1430 SETI 后缀自动机/后缀数组 不重叠子串的个数
题目求不重叠子串的个数。 一开始看错题第一反应就是用SAM来解，求出right集，如果出现次数超过1次就统计。 不过本题要求的是不重叠的子串，因此在求right集时，顺便维护两个值，每个结点所能表示的所有原串的终点的最小值和最大值。 最后遍历所有结点统计答案。O(n) 如果用SA来做的话就是枚举所有...
Bzoj4480: [Jsoi2013]快乐的jyy 广义后缀自动机 倍增 哈希 manacher
国际惯例的题面:有人说这是回文自动机的板子题，然而我是不会这种东西的。于是，我选择用更一般性的方法去解决这个题，就是那一堆东西了。首先，我们把两个串同时插入一个广义SAM里，拓扑排序维护每个节点的parent树的子树中来自两个串的right集合的大小sizA和sizB。同时倍增求出parent树上每...
BZOJ 2946 [Poi2000]公共串 (二分+Hash/二分+后缀数组/后缀自动机)
求多串的最长公共字串.法1: 二分长度+hash 传送门法2: 二分+后缀数组 传送门法3: 后缀自动机拿第一个串建自动机,然后用其他串在上面匹配.每次求出SAM上每个节点的最长匹配长度后,再在全局取最小值(因为是所有串的公共串)就行了.CODE#include<bits/stdc++.h&g...
【bzoj2946】[Poi2000]公共串 后缀自动机
[Poi2000]公共串Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 1386 Solved: 620[Submit][Status][Discuss]Description 给出几个由小写字母构成的单词，求它们最长的公共子串的长度。任...
BZOJ 2946: [Poi2000]公共串( 后缀自动机 )
一个串建后缀自动机, 其他串在上面跑, 然后用当前串跑的去更新全部---------------------------------------------------------------------------#include<cstdio>#include<cstring&...
hdoj5769后缀自动机版本
网上的题解都是后缀数组，我来个后缀自动机题解。建好后缀自动机后由于后缀自动机是单向的，那么dfs一遍记录各节点的size,要保证一个节点只经过一次才是O(n)，否则是O(n^2)。表示这个节点及后面还有几个节点。然后再来个ans数组，再dfs一次。这次如果走的是题目要的字母（记c),那么ans[x]...
【CF666E】Forensic Examination - 广义后缀自动机+线段树合并
广义SAM专题的最后一题了……呼题意：给出一个长度为$n$的串$S$和$m$个串$T_{1\cdotsm}$，给出$q$个询问$l,r,pl,pr$，询问$S[pl\cdotspr]$在$T_l\cdotsT_r$中哪个串出现次数最多，出现了多少次。$1\leqn,q\leq10^5,1\leqm,...
cf666E. Forensic Examination(广义后缀自动机 线段树合并)
题意题目链接Sol神仙题Orz后缀自动机+线段树合并首先对所有的\(t_i\)建个广义后缀自动机，这样可以得到所有子串信息。考虑把询问离线，然后把\(S\)拿到自动机上跑，同时维护一下最长能匹配的位置，对于每个以\(i\)位置为右端点的询问我们需要找到\(len\)最小的状态满足\(len[sta]...
后缀自动机（SAM）学习笔记
目录定义SAM的状态集一些性质SAM的后缀链接SAM的转移函数一些性质算法构造构造方法时间复杂度证明状态的数量转移的数量代码实现实际应用统计本质不同的子串个数计算任意子串出现次数统计所有本质不同子串的权值和求循环串在原串中出现次数SAM上博弈与trans上查询题意题解此篇博客大部分内容来自于hiho...
BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡 广义后缀自动机 后缀自动机 字符串
https://www.lydsy.com/JudgeOnline/problem.php?id=3926广义后缀自动机是一种可以处理好多字符串的一种数据结构（不像后缀自动机只有处理一到两种的时候比较方便）。后缀自动机可以说是一种存子串的缩小点数的trie树，广义后缀自动机就是更改了一下塞点的方式让...
51nod 1292 字符串中的最大值V2（后缀自动机）
题意：有一个字符串T。字符串S的F函数值可以如下计算：F(S)=L*S在T中出现的次数（L为字符串S的长度）。求所有T的子串S中，函数F(S)的最大值。题解：求T的后缀自动机，然后所有每个后缀自动机的结点u求出endpos[u]*maxlen[u]中的最大值即可#include<iostrea...
洛谷P4248 [AHOI2013]差异(后缀自动机求lcp之和)
题目见此题解：首先所有后缀都在最后一个np节点，然后他们都是从1号点出发沿一些字符边到达这个点的，所以下文称1号点为根节点，我们思考一下什么时候会产生lcp，显然是当他们从根节点开始一直跳相同节点的时候，所以思路就是先找出每个节点被几个后缀经过，这显然把边反转倒着找就可以了，然后他会被出现次数sz个...
【hihoCoder 1466】后缀自动机六·重复旋律9
http://hihocoder.com/problemset/problem/1466建出A串和B串的两个后缀自动机对后缀自动机的每个状态求出sg值。求出B串的\(sum(x)\)，表示B有多少子串的sg值等于x（用拓扑序求）。对A串的每个状态，求出B串有多少子串的sg值不等于这个状态的sg值，再...
CF666E Forensic Examination [后缀自动机，线段树合并]
洛谷Codeforces思路最初的想法：后缀数组+区间众数，似乎并不能过。既然后缀数组不行，那就按照套路建出广义SAM，然后把\(S\)放在上面跑，得到以每个点结尾会到SAM上哪个节点。询问时对于\(p_r\)所在的节点，倍增往parent树上跳，找到包含\([p_l,p_r]\)的最小区间。然后统...
POJ1509 Glass Beads 【后缀自动机】
题目分析：模板练手。看最长能走多远。代码:#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>usingnamespaces...
[Luogu5161]WD与数列(后缀数组/后缀自动机+线段树合并)
https://blog.csdn.net/WAautomaton/article/details/85057257解法一：后缀数组显然将原数组差分后答案就是所有不相交不相邻重复子串个数+n*(n-1)/2。答案=重复子串个数-相邻或相交重复子串个数。前者单调栈直接求解，注意细节，重点在后者。由于是...
CF666E Forensic Examination（后缀自动机+线段树合并）
给你一个串S以及一个字符串数组T[1..m]，q次询问，每次问S的子串S[pl..pr]在T[l..r]中的哪个串里的出现次数最多，并输出出现次数。如有多解输出最靠前的那一个。我们首先对m个字符串数组建出后缀自动机，然后我们可以通过跳trans边找到S前i个字符代表的前缀的最长后缀。我们要找的是S[...
[CF666E]Forensic Examination：后缀自动机+线段树合并
分析用到了两个小套路：使用线段树合并维护广义后缀自动机的\(right\)集合。查询\(S[L,R]\)在\(T\)中的出现次数：给\(T\)建SAM，在上面跑\(S\)，跑到\(R\)的时候先判匹配长度是否\(\geqR-L+1\)，如果是则跳parent使\(maxlen(x)\geqR-L+1...
BZOJ3413: 匹配(后缀自动机 线段树合并)
题意题目链接Sol神仙题Orz后缀自动机+线段树合并。。。首先可以转化一下模型(想不到qwq)：问题可以转化为统计\(B\)中每个前缀在\(A\)中出现的次数。(画一画就出来了)然后直接对\(A\)串建SAM，线段树合并维护一下siz就行了#include<bits/stdc++.h>u...