先给个这道题的链接：spoj bzoj
最近我重新复(学)习了一遍后缀自动机，发现原来有好多的东西已经全都忘掉了，这道题是我做kuangbin专题加强版时遇到的最难的一道题，也是到目前为止基本上是我写过的代码里最长的一个(树套树都没这么长啊QAQ)，写了我整整一天
我做的专题是：打个广告，好像打不开，网址是 https://vjudge.net/contest/214869#overview
代码长度：压行以后，把debug的全删掉250行，加上就320行了，如果format一下就更长了，快400行了吧
时间：bzoj现在排名第4，2100ms，vjudge（spoj）上570ms，现在是第2，还是比较快的（orz rank1的大佬，好像是基本一样的方法，但是看都看不懂）
update:加了个输入挂，然后spoj->260ms，加了个输出挂，然后spoj->250ms，bzoj->1412ms，全都rank1了好爽啊，想要输入输出挂代码的可以去vjudge上找下，rank1感觉可能是由于机器升级了，这道题又没啥人做造成的
做法：主要参考了两个blog：blog1 blog2 还有这个blog3
虽然我由于我太菜，基本思路全都是参考的第二个blog，感觉写的都和第二个blog里的都差不多了，这里可以认为基本上是对那个blog的补充
题意我就不详细说了，主要是说：
两组串的set，S里是格式串，T串是目标串，求T中某串Ti在S中Si出现了几次
S串的增加方法是从一个已有的串往后加个字符，生成新串
T串的增加方法是从一个已有的串向前或者向后加个字符；或者两个已有的串连到一块生成新串
详细讲讲做法：（在线的我实在是不会啊，感觉怎么也不能直接做，或许后缀平衡树用替罪羊树均摊可做？感觉不太对的样子）
首先，我们知道一个定理，后缀自动机的fail树是反串的后缀树，然后我们利用这个定理来做这道题：
在线做的话，S串和T串都是会变化的，虽然S串变化不大，但是离线显然会简化问题：
然后我们就离线做了：
由于：第一，一个字符很简单就能找到在任意串出现的次数，第二，T串的增加方式和S串是一样的，所以我们只需要解决一个问题：两个串Ta和Tb，而且你知道Ta串在任意串中出现的次数和Tb串在任意串出现的次数，怎样维护加起来的串在任意串中才出现的次数呢？（这里维护任意串是因为如果只维护一个串或者某些串，我不知道怎样能让复杂度是对的）
这里我自己觉得只有hash一下才可以做，然后就GG了，但是其实有个如果从后缀树来反着看的话，有一些性质：
首先，如果将trie的串从小到大加到后缀自动机上的话，有个性质就是加入的点fail上长度是不一样的，也就是说从fail网往上看，每个点代表的串都不同，而且fail树上从0往下看每个开始的字符一定不同，否则就矛盾了
然后如果我们在trie上bfs，同时加进后缀自动机，就能够把trie按后缀排序了（这可能是个套路，然后我太菜并不知道）
那么我们对于T串的每一个串维护一个[L,R]，表示作为一个串能在之前的后缀上的rank，然后合并时二分一下，然后在trie上求kth-father，就能够得出连起来的[L',R'] 了（二分然后将前串的rank和kth-father的比一比，这里的二分写的我好难受啊）
然后，由于这里求father比较多，或者说特别多，如果这里倍增来求kth-father，常数较大，而且多个log，坑爹的卡常（或者本意就是要卡这个log），导致过不了这道题。如果用32位的预处理是可过的，但是有更好的方法：kth-father有个利用长链剖分，O(nlogn)预处理，O(1)查询的ladder+倍增的方法，用这个方法就能过了(我写的时候还写挂了好长时间。。注意ladder只有top相等时要push)，链接：zqc的blog
下面给下我的代码（为了清楚，不带输入输出挂）
代码
#include
#include
#include
#include
#include
#include
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
