BZOJ3413: 匹配(后缀自动机 线段树合并)
题意题目链接Sol神仙题Orz后缀自动机 + 线段树合并。。。首先可以转化一下模型(想不到qwq)：问题可以转化为统计\(B\)中每个前缀在\(A\)中出现的次数。(画一画就出来了)然后直接对\(A\)串建SAM，线段树合并维护一下siz就行了#include<bits/stdc++.h>...
模板—字符串—后缀自动机（后缀自动机+线段树合并求right集合）
模板—字符串—后缀自动机（后缀自动机+线段树合并求right集合）Code:#include <bits/stdc++.h>using namespace std;#define N 100010map <int,int> son[N<<1]; char str[...
SPOJ LCS2 后缀自动机
多串的LCS,注意要利用拓扑序更新suf的len。我用min,max,三目会超时，所以都改成了if,else#pragma warning(disable:4996)#include<cstring>#include<string>#include<iostream&g...
康复计划#1 再探后缀自动机&后缀树
本篇口胡写给我自己这样的东西都忘光的残废选手 以及那些刚学SAM，看了其他的一些东西并且没有完全懵逼的人（初学者还是先去看有图的教程吧，虽然我的口胡没那么好懂，但是我觉得一些细节还是讲清楚了的）大概是重复一些有用的想法和性质，用以加深印象吧…如果可以的话希望也能理解得更透彻一点…1、如何设计出一个后...
uva 719 Glass Beads（后缀自动机）
【题目链接】 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=524&page=show_problem&problem=660【题目大意】给出一个字符串，求...
BZOJ 3676 [Apio2014]回文串 (后缀自动机+manacher/回文自动机)
题目大意：给你一个字符串，求其中回文子串的长度*出现次数的最大值明明是PAM裸题我干嘛要用SAM做回文子串有一个神奇的性质，一个字符串本质不同的回文子串个数是$O(n)$级别的用$manacher$的思想分析一下，$maxright$指针向右扩展才会产生新的回文串其它的回文串都根据之前求得的信息得到...
【字符串数据结构后缀系列Part2】后缀自动机学习笔记
由SA到SAM无疑是一个难度极大的跨越. 听说SAM非常厉害可以线性构造SA再也不需要 O(nlogn) 的倍增构造SA(虽然由于常数速度和 O(nlogn) 并没有太大区别233)简直太神啦有木有>w<————————————–线 割 分 是 我 >ω&l...
bzoj 3676: [Apio2014]回文串【后缀自动机+manacher】
用manacher找出本质不同的回文子串放在SAM上跑#include<iostream>#include<cstdio>#include<cstring>#include<string>using namespace std;const int N=...
回文树&后缀自动机&后缀数组
KMP，扩展KMP和Manacher就不写了，感觉没多大意思。 之前感觉后缀自动机简直可以解决一切，所以不怎么写后缀数组。 马拉车主要是通过对称中心解决问题，有的时候要通过回文串的边界解决问题，这个时候回文树就用到了，又好写，又强大。 之前整理过一篇后缀自动机的。感觉还要整理一下，顺便把回文树，后缀...
后缀自动机(SAM)速成手册！
正好写这个博客和我的某个别的需求重合了。。。我就来讲一讲SAM啦qwq后缀自动机，也就是SAM，是一种极其有用的处理字符串的数据结构，可以用于处理几乎任何有关于子串的问题，但以学起来异常困难著称（在机房里，最先学会SAM的永远是大佬（比如litble和zyf（他在退役前就学了）））。但是！！！当你学...
2018.12.22 spoj7258 Lexicographical Substring Search（后缀自动机）
传送门samsamsam基础题。题意简述：给出一个串，询问第kkk大的本质不同的串。然而这就是弦论的简化版。我们把samsamsam建出来然后贪心选择就行了。代码：#include<bits/stdc++.h>#define ri register intusing namespace ...
后缀自动机&回文自动机学习笔记
在学了一天其实是边学边摆之后我终于大概$get$后缀自动机了,,,就很感动,于是时隔多年我终于决定再写篇学习笔记辽$QwQ$$umm$和$FFT$学习笔记一样,这是一篇单纯的$gql$的知识总结博,对新手并不友好,想学$SAM$的话我是推荐几篇博客:1 2 3(没有$hihocoder$主要我$ji...
[TJOI2015]弦论(后缀自动机)
/*一道在树上乱搞的题目建立出parent树来， 然后就能搞出每个节点往后能扩展出几个串， 至于位置不同算同一个的话就强制让right集合大小为1即可然后在树上类比权值线段树找第k大26分统计一下即可 */#include<cstdio>#include<algorithm>...
spoj 7258 Lexicographical Substring Search (后缀自动机)
spoj 7258 Lexicographical Substring Search (后缀自动机)题意：给出一个字符串，长度为90000。询问q次，每次回答一个k，求字典序第k小的子串。解题思路：构造出sam后，类似splay求前驱的做法，不断的逼近答案。我们知道，sam里从s走到某一节点即为一个...
bzoj 2555 SubString——后缀自动机+LCT
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2555要维护 right 集合的大小。因为 fa 会变，且 fa 构成一棵树，所以考虑用 LCT 来维护……和平常写的 LCT 不太一样。因为要的值是原树上子树里的值，所以没有 makeroot...
SPOJ1811 LCS - Longest Common Substring(后缀自动机)
A string is finite sequence of characters over a non-empty finite set Σ.In this problem, Σ is the set of lowercase letters.Substring, also called fact...
CF1073G Yet Another LCP Problem 后缀自动机 + 虚树 + 树形DP
题目描述 记 $lcp(i,j)$ 表示 $i$ 表示 $i$ 这个后缀和 $j$ 这个后缀的最长公共后缀长度 给定一个字符串，每次询问的时候给出两个正整数集合 $A$ 和 $B$，求 $\sum_{i\in A,j\in B}lcp(i,j)$ 的值. 题解： 对反串建立后...
后缀自动机（SAM）+广义后缀自动机（GSA）
经过一顿操作之后竟然疑似没退役0 0你是XCPC选手吗？我觉得我是！稍微补一点之前丢给队友的知识吧，除了数论以外都可以看看，为Dhaka和新队伍做点准备...不错的零基础教程见 IO WIKI - 后缀自动机，这篇就从自己的角度总结一下吧，感觉思路总是和别人不一样...尽量用我比较能接受的语言和逻...
【后缀自动机】洛谷P3804模板题
题目描述给定一个只包含小写字母的字符串S,请你求出 S 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值。输入输出格式输入格式：一行一个仅包含小写字母的字符串S输出格式：一个整数，为 所求答案输入输出样例输入样例#1：abab输出样例#1：4说明对于10%的数据，|S|<=100...
HIHOcoder 1466 后缀自动机六·重复旋律9
思路后缀数组+博弈论的好题，首先对两个串都建出SAM，然后题目的要求实际上就是在SAM的trans上转移即可DAG的博弈是经典问题，然后dfs求出SG函数，两个游戏的组合就是把SG函数异或起来，异或是0就是先手必败，不是0就是先手必胜然后要求先手必胜，所以就是求异或不为0接下来递推的求出第k大的串即...