给定一个长度为 n 的字符串，让求出它的第 $k$ 小子串是什么。每次除字符串之外还会给定两个参数 $t $和 $k$ ，$t$ 为 $0$ 则表示不同位置的相同子串算作一个, $t$ 为 $1$ 则表示不同位置的相同子串算作多个。数据范围 $n\le 5*10^5$ $t\in {0,1}$ , $k \le 10^9$.
后缀自动机板子题。我们知道每一个子串放在sam上跑一定可以走到一个合法节点，反过来说任意一个节点一定代表了一批能走到这儿的子串。那么我们可以想办法把到达每个节点有多少种子串用dag图上dp的方式求出来，然后在t=1的时候，根据sam的性质，给每个dp值再乘以一个 $|endpos|$ 就可以了。学习到的是比我原来板子更快的拓扑排序方式。。。直接用len结果在数组里排序，比起用queue来常数小了很多。另外还纠正了自己的对于sam拓扑序的一个错误认识，他其实无论是slink还是dwag的拓扑序都是一样的，因为无论哪种都一定是从小的子串往大的走。
继续阅读“[SAM][dp][拓扑排序][模板] 洛谷 P3975 TJOI2015 弦论”
又是一个Trie图上找递推关系的题~只不过这次是单字符串做一个Trie图（这样的话用扩展kmp也可以8
把样例研究一下再结合Trie图基本就能确定出等式关系了，设dp[i]为
现在在Trie图上的节点i，还需要走多少步（期望意义下）才能凑出给定的字符串
容易知道当走到尽头的时候dp[n]=0;其他的项地推关系可以表示为dp[u]=1+\sum i/n*dp[v] ,其中v是u走向的下一个节点。
以样例n=2,s=”ABA”为例，Tried图和方程组如下
解这个方程组可得dp[0]=5,就是我们要的结果了。
具体代码实现的时候，直接对每个结点都把转移记录下来，然后用高斯消元解方程即可。注意应该把n乘到等式左边，然后用整数的高斯消元，不然会有误差wa。
继续阅读“[AC自动机][Trie图][期望DP][高斯消元] Generator UVALive 3490”
题目链接： Password Suspects
这题让我回想起了某现场赛被某大佬支配的恐惧
感觉是dp，而且这个子串的数据量一看就是状压，然后在推转移方程的时候死活推不出来一个不交叉的。可耻的搜了题解，看到大佬们的标题：AC自动机+DP
我就
~~其实是常见的一种操作只是我太久没做过字符串的题目了~~
在思考递推方程的时候就一直在纠结前缀与后缀重合的这种情况怎么表示状态，然后忽然意识到ac自动机（更确切的说是Trie图）就是可以唯一的确定一个匹配状态的数据结构！这种题一般都是给定一些字串，然后给出一些约束条件，比如要求
题意：给出n个字符串，要求求出所有的前后缀组成的字符串种类数。
思路：比较简单的一题。 用Trie存储所有的字符串，可以算出所有不同的前缀数，然后把字符串全部反向再插入到另一个Trie，得出所有的后缀数量。二者相乘可以得到所有的可能结果，但是会有重复，所以要去重。去重也很简单，画一画样例可以看出来一定是算出来两个Trie里面的相同的字符出现的次数，每一个字符结点出现一次就会有一个重复，这样减去所有的重复即可。但是直接这样算会有错误，因为可能会产生有的前缀为空后缀为一个不完整字符串，这样是不满足题目要求的，所以在统计结点数量的时候只统计长度大于1的结点（在Trie里深度大于1），然后这样构造出来的全部是满足要求的字符串而且没有重复，但是仍然有一个bug是有的字符串只有一个字符，而上述方法是只能构造出来最小长度为2的字符串的，因此要另外处理这些长度为1的字符最后加到答案里。
题意要求所有的T中的循环串在S中出现了多少次，多次出现重复计数。
先考虑处理循环串，我们可以把循环串往后复制一遍变成定长单串，这时候如果我们可以把处理定长单串的方法搞出来就也能搞出来循环了。现在考虑的是对于一个串T，以T[i]为结尾的长为n的串出现了几次。很容易想到用endpos的大小去求，所以应该先把endpos大小求出来，之后就是应该确定是哪个endpos。可以先考虑如何求出对于T[i]来说与S的最长公共子串，这时候只要在SAM上顺着fa树走一直到走到原点或者有可以往后转移就可以了。如果走到了根节点还是没有能转移的，那就说明就没有这个字符，直接全0就可以了。注意这时候的长度可能过大，也就是stl超过了n，而在计算的时候应该是只需要“刚刚好包含长度为n”的那个状态节点的endpos。所以需要再顺着fa往前跳到fa的len小于n就可以了。然后这时候还有一个重复计算的问题，这是由于循环串可能有重复产生的，这时候我们就得给同样的条件打上标记了，而怎么判断是同样的呢？显然当串相同的时候一定会走到相同的节点上，只需要在最后的+环节打标记就可以了。
wa点主要出在指针和状态下标的转换上以及数组的长度上，注意循环串要复制一遍的话得是2倍长度。。。emmm
这个题在codeforces上有几乎一模一样的：http://codeforces.com/contest/452/problem/F
cf上的题说的是考虑长度为3的等差序列，bzoj这个说的是等差序列其实也是找长度为3的，因为显然能找到长度大于3的肯定也能找到等于3的。cf那个题有个假算法可以过掉所有数据，就是暴力枚举中点，然后往左右延伸的时候不超过5个就行。。之所以能这么做是因为这个题目要想构造出来NO的数据确实很难。。不过假算法依然是假算法。。
正解是每次出现过一个点之后把他在线段树上值变为1，然后求一个中点左右两边有没有相同的时候需要判断左右两边是不是完全一样，如果不是一定有解。这里判断的方法是hash。。。分别在两个线段树上维护正反两个方向的左右01字符串的hash值就可以了。
wa点：首先是对于这种多项式形式的线段树合并的时候要分三种情况，完全在左/完全在右/跨越中点；其次是跨越中间点的情况下一定要考虑清楚应该累加的数值是多少。。在这里是pw[mid-max(ql,l)]；最后是当ai==1和ai==n时候的特判，这时候不能query，但是必须update，我一开始写了单独处理1，然后i从2开始循环，后来忽然意识到a1并不一定等于1啊。。。傻了。。。
https://hihocoder.com/problemset/problem/1457
要求求出来n个串中所有子串的十进制和。
考虑单个串的情况：顺着sam的边走的话，一个点的所有字串等于它所有的父节点的字串+c，c为从父节点转移来的路径字符，由十进制的性质可以知道当前节点（设为st）的和为则求出sam状态转移图的拓扑序然后刷sum即可；
多个串的情况：考虑把多个串合并为1个串，每两个串之间以‘9’+1填充（也就是: )，然后建立sam。此时要求出sam每个状态中有多少个不含：字符的子串，这里用到了一个性质就是，这个值恰好就是从初始状态S到状态st的所有”不经过冒号转移的边”的路径数目，而有向无环图上的路径数目也是一个经典的拓扑排序问题！
由此只需求拓扑序的过程中把有效子串个数求出来就行了。
wa点的话，注意第一次调用sam前要用init函数初始化。另外，拓扑排序无需纠结数据结构条件是指向父节点还是从父节点指向子节点。
继续阅读“[SAM][多串][不同子串十进制求和][拓扑排序] hihocoder #1457 : 后缀自动机四·重复旋律7”
http://hihocoder.com/problemset/problem/1449
需要在O(n)时间内求出所有长度为k的字串中出现次数最多的字串的出现次数。这里的话首先肯定是要求出来endpos的大小了，球的方法是利用fa树上的不同的st之间的包含关系和子树之间的交集为空的性质。这样的话要想求出来某个点的endpos大小只需要知道它的子节点的endpos大小就行了，另外还有一种需要特判的情况就是当st包含S的前缀的时候需要再额外+1，因为这个前缀是后面的节点没有包含到的。
推的过程的话，首先求出来拓扑序，然后从后往前刷fa节点的cnt即可。但是如果就这样的话，要用朴素的算法求出来每个substring的长度还是需要n²的复杂度，仍然会卡住。然后这里有一个性质那就是长度短的substring中的最大值一定不会比长度长的小，然后我们只需要更新每个节点对应的maxlen的最大值就可以了，然后从后往前更新最大值。为什么这么做是对的？首先每个st里最大值那个点肯定是对的，然后每两个更新点之间的那一段一定是被某个右端点包含在内的一个st里的连续的一段，所以这些点其实和那个右端点的大小其实是一样的，刷过去肯定是对的。
#include<iostream>
#include<vector>
#include<cstring>
#include<map>
#include<string>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn=1000005;
const int mod=1e9+7;
const int CHAR=26;
struct sam_node
{
sam_node * fa,*nxt[CHAR];
int len;
bool flag;
//LL cnt;
void clear()
{
fa=0;
flag=0;
memset(nxt,0,sizeof(nxt));
//cnt=0;
}
int cnt()
{
return len-fa->len;
}
} pool[maxn<<1];
sam_node *root,*tail;
sam_node* newnode(int len)
{
sam_node* cur=tail++;
cur->clear();
cur->len=len;
return cur;
}
void sam_init()
{
tail=pool;
root=newnode(0);
}
sam_node* extend(sam_node* last,int x)
{
sam_node *p=last,*np=newnode(p->len+1);
while(p&&!p->nxt[x])
p->nxt[x]=np,p=p->fa;
if(!p)
np->fa=root;
else
{
sam_node* q=p->nxt[x];
if(q->len==p->len+1)
np->fa=q;
else
{
sam_node* nq=newnode(p->len+1);
memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
nq->fa=q->fa;
q->fa=np->fa=nq;
while(p&&p->nxt[x]==q)
p->nxt[x]=nq,p=p->fa;
}
}
np->flag=1;
return np;
}
char ori[maxn];
sam_node *End[maxn];
LL cnt[maxn<<1];
int deg[maxn<<1];
int topsort[maxn<<1],t;
LL ans[maxn];
int Len;
void solve()
{
sam_node* cur;
int len=tail-pool;
queue<int> Q;
for (int i=1; i<len; i++)
{
cur=pool+i;
deg[cur->fa-pool]++;
}
for (int i=1; i<len; i++)
{
if(!deg[i])
Q.push(i);
}
t=len-1;
int dif;
while(!Q.empty())//topsort
{
cur=pool+Q.front();
Q.pop();
topsort[t--]=cur-pool;
dif=cur->fa-pool;
deg[dif]--;
if(!deg[dif]&&dif)
Q.push(dif);
}
for (int i=len-1; i; i--)
{
int x=topsort[i];
cur=pool+x;
if(cur->flag)
cnt[x]++;
if(cur->fa)
cnt[cur->fa-pool]+=cnt[x];
}
for (int i=1; i<len; i++)
{
cur=pool+i;
ans[cur->len]=max(ans[cur->len],cnt[i]);
}
for (int i=Len-1; i; i--)
{
ans[i]=max(ans[i],ans[i+1]);
}
}
int main()
{
//freopen("1.txt","r",stdin);
//freopen("out.txt","w",stdout);
//gets(ori);
scanf("%s",ori);
Len=strlen(ori);
sam_init();
End[0]=root;
for (int i=1; i<=Len; i++)
{
End[i]=extend(End[i-1],ori[i-1]-'a');
}
solve();
for (int i=1; i<=Len; i++)
printf("%lld\n",ans[i]);
return 0;
}
/*
*/
这个题当时tle到哭，心态爆炸，也几乎直接导致了没去看很简单的G，心情复杂。
这个判重刚好卡unordered_set，怎么都过不了，只能自己手写Hash判重。另外一个优化的点就是一定要边Manachar边计算，我一开始写的跑一遍Manacher之后枚举中点然后计算左右端点（那不就退化成n^2了嗯我当时就这么傻）。一边Manacher一边做，好处就是关于某个点对称的重复的回文串只会被算一次！这也是Manacher自身的算法决定的。。这个题其实出题人就是想让这么做的，不然要想计算所有出现的回文串的（不判重）MOD，应该是只能n^2吧。。（或许SAM可以？我没想过）。
需要巩固的地方：字符串Hash，字符串子串预处理（取模等），Manacher的原理的深刻理解。
继续阅读“[字符串][Manacher][Hash] 2018ICPC 南京网络赛 I Skr”
Huh，比赛的时候花了三个小时把这个正解是用后缀自动机的题肝了出来，我也不知道我怎么做到的。
想了很多策略之后发现自己是错的就很难受，最后终于想到正确策略：在height数组上做一个长度为k的滑窗，每次检查滑窗两端点之外的height是否比这一整段内的最小值大，注意这里面的一整段最小值M就是这一整段的公共最长公共前缀的长度，这个东西和他的前缀是在这里出现了k次的，那么怎么知道他是不是在滑窗外面出现呢，和两端点的height比较一下就行了，取两端点中的最大值P，这个说明是之外的点与滑窗两个端点的最大公共前缀，而所有的在滑窗内的满足P<len<=M的前缀都是仅出现了一次的子串！！！
wa的话，需要特判k为1的情况，，因为height这个数组是个间隔定义的东西，所以这种只有一个的需要单独处理，这时候实际上区间内的最长公共前缀就是排名在此的后缀本身