Daniel__d的博客

工艺-后缀自动机 题目描述 题解 对于字符集大小不为常数的后缀自动机题，可以暴力建mapmapmap 首先倍长序列，对倍长过后的序列建后缀自动机，然后根据贪心，直接从根节点遍历n次输出答案即可（其实还是有点不懂） （坑：数组必须开到1e6，不知为啥） 代码实现 #include<bits/stdc++.h>//SAM #define M 1000009 using namespace...

SP1812-LCS2-后缀自动机 题目描述 题解 对于一个串构建SAMSAMSAM 每个串依次进行匹配 同时记录tr[i].maxntr[i].maxntr[i].maxn表示走到了iii节点能够匹配上的最长公共子串的长度 当然，每个串的tr[i].maxn可以更新tr[tr[i].fa].maxntr[tr[i].fa].maxntr[tr[i].fa].maxn 所以需要拓扑排序 对于每个...

SPOJ1811-LCS-后缀自动机 题目描述 题解 首先对AAA串建立一个后缀自动机，然后让BBB串一个一个字符去匹配； 匹配方式： 首先置len=0len=0len=0,然后从根节点开始遍历下去 1，如果当前节点存在，就len++len++len++，继续遍历下一个节点 2，如果当前节点不存在，就跳该节点的fafafa， 2.1，如果跳的过程中找到了该节点，那么就继续从该节点遍历下去，len...