给定一个长度为 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 弦论”
题意要求所有的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
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;
}
/*
*/