rt，会罗列一些近期做的串串题
一些题单：
清烛 - 字符串
Hoks -『提高进阶篇』ACAM。
Polaris_Australis - 后缀数组，后缀自动机，回文自动机题单
hs_black - 【字符串】后缀系列
一些博文：
alex-wei - 常见字符串算法 好像是老文章了？不过里面有修订版索引。
Part 1
P3966 [TJOI2013] 单词
ACAM 练手题，先考虑给这个文本串两两之间用一个没出现过的符号隔开就可以搞出论文，然后建出字典树，然后用论文去跑，那么如果当前节点在 \(x\)，那么所有 \(fail_x\) 那些单词都可以作为这个的后缀，所以先全打标记，最后从后往前释放即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO
{template<typename T>void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}template<typename T,typename... Args>void read(T &_x,Args&...others){Read(_x);Read(others...);}const int BUF=20000000;char buf[BUF],to,stk[32];int plen;#define pc(x) buf[plen++]=x#define flush(); fwrite(buf,1,plen,stdout),plen=0;template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 2e6+10,M = 210;
int n,tr[N][27],c[M],fail[N],b[N],cnt = 1,o,cnt1,st[N],cnt2,x,y,z;
string s,t;
ll sum[N];
queue<int>p;
inline int insert(int x)
{for(int j = 1;j <= cnt1;j++) {if(!tr[x][b[j]]) tr[x][b[j]] = ++cnt;x = tr[x][b[j]];}return x;
}
inline void fail_build()
{for(int i = 0;i < 26;i++) if(tr[0][i]) p.push(tr[0][i]);while(!p.empty()){x = p.front(),p.pop(); st[++cnt2] = x;for(int i = 0;i < 26;i++)if(tr[x][i]) p.push(tr[x][i]),fail[tr[x][i]] = tr[fail[x]][i];else tr[x][i] = tr[fail[x]][i];}
}
inline void query(int x){ for(int j = 1;j <= cnt1;j++) x = tr[x][b[j]],sum[x]++; }//注意到要么有，要么是fail，直接取tr
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);read(n);for(int i = 1;i <= n;i++) {cin >> s,cnt1 = s.size(),t += s,s = ' '+s; t += 'A';for(int j = 1;j <= cnt1;j++) b[j] = s[j]-'a';c[i] = insert(0);} fail_build();cnt1 = t.size(),t = ' '+t;for(int j = 1;j <= cnt1;j++) b[j] = t[j]-'a';query(0);for(int i = cnt2;i >= 1;i--) sum[fail[st[i]]] += sum[st[i]];for(int i = 1;i <= n;i++) print(sum[c[i]]),pc('\n');flush(); return 0;
}