关键词：
以下全部是笔记，不要看了
注意：要求的不是"有多少不同的子串是..."，相同的要重复计算贡献。
例如：
3 2
aca
a
c
答案是3 1 1第一个串中两个a都出现了两次，c出现了两次，所以第一个的答案是3
广义后缀自动机模板。
各个串连起来中间加分隔符的不方便，一般都要加很多特判的。。。。
有的说不定就不能用了。。
可以直接对着多个串建。就一句话：
把很多串的SAM建到了一个SAM上，建每个串的时候都从root开始(last=root)
（也可以在trie上建，大概就是每个节点建时last就是父亲建完的np？没试过）
这样子复杂度可以证明是O(G(T))（好像要乘上字符集大小？没确定），G(T)为Trie树上所有叶子节点深度和，一定不超过所有串长度和
这样子插入的时候要判断是否已经存在对应节点，如果存在则考虑直接复用或者拆开后复用（就是普通的后缀自动机构建头上加一点跟后面很像的东西）
建出后缀树后，对于每一个节点维护一个集合，表示这个点到根的路径表示的后缀属于哪些字符串
对于每个节点计算贡献（一开始不直接将答案更新到对应字符串上，只更新到节点上，曾经陷入误区），就是如果它到根表示的后缀出现超过一次（就是以它为根的子树中各个集合的并集的size>1），那么产生len[t]-len[par[t]]的贡献，否则不产生贡献
最后还要一遍dfs把各个节点的答案加到以其为根子树中各个节点的答案上（将每个后缀的实际贡献更新为其各个前缀的贡献之和，达到求一个字符串所有子串贡献的目的）
这个地方我用了启发式合并来统计不同子串数量，好像有转换到序列上用树状数组做的方法。。。
最后每个串的答案就是其每个位置对应的后缀的答案之和
上面基本全是假的看不懂的。。。。还是意识流吧
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<queue> 5 #include<vector> 6 #include<set> 7 using namespace std; 8 int n,x; 9 char ss[100100],*sp=ss,*pp[100100]; 10 int le[100100]; 11 vector<int> tt[100100]; 12 namespace SAM 13 14 int mem,root; 15 int len[300100],par[300100]; 16 int trans[300100][26]; 17 void append(int ch,int& np) 18 19 int p=np; 20 //如果已经存在倒着的原串首部加上ch的串 21 if(trans[p][ch]) 22 23 int q=trans[p][ch]; 24 if(len[q]==len[p]+1)//如果没有被压过 25 np=trans[np][ch]; 26 else//如果被压了，要拆开 27 28 np=++mem;len[np]=len[p]+1; 29 par[np]=par[q];par[q]=np; 30 memcpy(trans[np],trans[q],sizeof(trans[np])); 31 for(;p&&trans[p][ch]==q;p=par[p]) trans[p][ch]=np; 32 33 return; 34 35 np=++mem;len[np]=len[p]+1; 36 for(;p&&!trans[p][ch];p=par[p]) trans[p][ch]=np; 37 if(!p) par[np]=root; 38 else 39 40 int q=trans[p][ch]; 41 if(len[q]==len[p]+1) par[np]=q; 42 else 43 44 int nq=++mem;par[nq]=par[q];par[q]=par[np]=nq; 45 memcpy(trans[nq],trans[q],sizeof(trans[nq]));len[nq]=len[p]+1; 46 for(;p&&trans[p][ch]==q;p=par[p]) trans[p][ch]=nq; 47 48 49 50 set<int> ss[301000]; 51 int in[300100]; 52 long long ans[300100]; 53 queue<int> q; 54 vector<int> son[300100]; 55 void dfs(int u) 56 57 for(int i=0;i<son[u].size();i++) 58 59 ans[son[u][i]]+=ans[u]; 60 dfs(son[u][i]); 61 62 63 void work() 64 65 int i,t; 66 for(i=1;i<=mem;i++) in[par[i]]++; 67 for(i=1;i<=mem;i++) 68 if(!in[i]) 69 q.push(i); 70 set<int>::iterator it; 71 while(!q.empty()) 72 73 t=q.front();q.pop(); 74 if(!t) continue; 75 if(ss[t].size()>=x) ans[t]=(len[t]-len[par[t]]); 76 if(ss[par[t]].size()<ss[t].size()) swap(ss[par[t]],ss[t]); 77 for(it=ss[t].begin();it!=ss[t].end();++it) 78 ss[par[t]].insert(*it); 79 in[par[t]]--; 80 if(in[par[t]]==0) q.push(par[t]); 81 82 for(i=1;i<=mem;i++) son[par[i]].push_back(i); 83 dfs(root); 84 85 86 long long anss; 87 88 int main() 89 90 int i,j,np;char *b,*ed; 91 scanf("%d%d",&n,&x); 92 SAM::root=++SAM::mem; 93 for(i=1;i<=n;i++) 94 95 scanf("%s",sp); 96 pp[i]=sp;le[i]=strlen(sp);sp+=le[i]; 97 np=SAM::root;b=pp[i];ed=pp[i]+le[i]; 98 for(;b!=ed;b++) 99 100 SAM::append(*b-\'a\',np); 101 SAM::ss[np].insert(i); 102 tt[i].push_back(np); 103 104 105 SAM::work(); 106 for(i=1;i<=n;i++) 107 108 anss=0; 109 for(j=0;j<tt[i].size();j++) anss+=SAM::ans[tt[i][j]]; 110 printf("%lld ",anss); 111 112 return 0; 113
[bzoj3277]串广义后缀自动机(代码片段)
3277:串TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 811 Solved: 329[Submit][Status][Discuss]Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k... 查看详情
bzoj3277串(代码片段)
...答案串。然后处理出每个点到根的树链上所有点的答案。代码：#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineN100050#definelllonglongintn,k;chars[N],sum[N];structnodeintpre,len,trs[28];intcnt;p[2*N];intuse[2*N],vis[2*N],ens[N],v[2... 查看详情
bzoj3277&bzoj3473串——广义后缀自动机(代码片段)
...；开2e5就可以，因为每次加入一个字符最多新增2个点。代码如下：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;typedeflonglongll;intconstxn=2e5+5;intn,K,cnt=1,go[xn][30],len[xn],fa[xn],vis[xn],tot[xn],lst;llf[xn... 查看详情
bzoj3277:串(代码片段)
Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。Input第一行两个整数n，k。接下来n行每行一个字符串。n,k,l<=10000... 查看详情
bzoj3473字符串&bzoj3277串
...同的子串多次出现算多次,如11aaa这组数据答案为6,贡献1WA.代码里有些部分是为了处理子串本质不同,可能没删干净.因为字符串的总长不超过10^5,那么后缀的个数也不超过10^5。一个长为x的后缀可以产生x个子串，其中在至少k个串中... 查看详情
bzoj3277串
TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 568 Solved: 233Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包... 查看详情
bzoj3277:串
Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。Solution出现\(k\)次的问题比较好解决,我们构出\(parent\)树,然后在上... 查看详情
并不对劲的bzoj3277
陈年老坑题意大概是有n个字符串，要求出每一个字符串的所有子串（不包括空串）在所有字符串（包括自身）中出现次数不少于k的有多少个。n,k,字符串总长<=100000。如果只有一个串的话，非常好办，直接把它建成后缀自动机... 查看详情
bzoj4503两个串(代码片段)
...计$26*3=78$次$FFT$。其实有更好的方法我放在下一篇博客里代码：#include<cmath>#include<cstdio>#include<cstring>#include<algorithm>u 查看详情
bzoj1396识别子串(代码片段)
...值mn。然后套上线段树维护区间最小值。基本就这样了。代码：#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#de 查看详情
bzoj1396识别子串(代码片段)
...区间取等差数列，区间取最小值分别线段树维护就可以了代码： #include<bits/stdc++.h>#defineILinline#definelllonglong#definerintregisterint#definerep(i,h,t)for(rinti=h;i& 查看详情
bzoj4503:两个串bitset(代码片段)
题目链接bzoj4503:两个串题解暴一发bitsetf[i][j]表示S[1..i]是否有个后缀能匹配T[1..j]那么假设S[i+1]能匹配T[s]，令f[i+1][s]|=f[i][s-1]所以预处理理出每个字符能匹配T的哪些位置,设为[c]那么f[i]=((f[i-1]<<1)|(1<<1))&mat[S[i]]直接在mat... 查看详情
[bzoj1396]识别子串(代码片段)
题面：看起来有点吓人实则不然用SA或是SAM都可以过SAM做法：(哪天有空再补)SA做法：求完SA之后，对于每一个后缀$i$以这个后缀为起点的最短唯一子串长度应该是$max(hei[i],hei[i+1])+1$之后用线段树覆盖对应区间就行⑨：BakaBaka~当然... 查看详情
bzoj3325密码-manacher(代码片段)
题目传送门 需要root权限的传送点题目大意 已知一个串，以每个字符为中心的最长回文串长，以及每两个字符中间为中心的最长回文串长。求字典序最小的这样一个串。题目保证有解。 考虑Manacher的过程，假设当前扩... 查看详情
bzoj2553禁忌(代码片段)
题意：给定n个禁忌串。由字母表中的前alp的字母组成长度为len的字符串中，定义某个字符串的伤害为存在的一种分割方法使得其中禁忌串的数量的最大值（同一个禁忌串出现两次就算两次）。问期望伤害？n<=5,禁忌串长度<=1... 查看详情
bzoj3790神奇项链(代码片段)
...回文，然后贪心发现这是线段覆盖。排序然后搞就行了。代码：#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;chars0 查看详情
bzoj2946poi2000公共串后缀自动机（多串最长公共子串）(代码片段)
题意概述：给出N个字符串，每个串的长度<=2000（雾。。。可能是当年的年代太久远机子太差了），问这N个字符串的最长公共子串长度为多少。(N<=5) 抛开数据结构，先想想朴素做法。设计一种稳定的暴力算法。可以想到... 查看详情
bzoj1396:识别子串sam+线段树(代码片段)
建个SAM，符合要求的串显然是|right|==1的节点多代表的串，设si[i]为right集合大小，p[i]为right最大的r点，这些都可以建出SAM后再parent树上求得然后对弈si[i]==1的点，考虑它所代表的串是s(p[i]-dis[i]+1,p[i])~s(p[i]-dis[fa[i]],p[i])，然后对于p... 查看详情