关键词：
题解：
对于多串的子串，我们可以建出广义后缀自动机。
由于本题询问的是（子串出现次数>=k）×len的总和，就将所有串扔到自动机中，爆跳pre并标记。每个点得到
一个经过次数cnt。
若cnt>=k，说明这个点压缩的所有子串都可以作为答案串。
然后处理出每个点到根的树链上所有点的答案。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100050 #define ll long long int n,k; char s[N],sum[N]; struct node int pre,len,trs[28]; int cnt; p[2*N]; int use[2*N],vis[2*N],ens[N],v[2*N]; struct SAM int tot,las; SAM()tot=las=1; void res()las=1; void insert(int c) int np,nq,lp,lq; np = ++tot; p[np].len = p[las].len+1; for(lp=las;lp&&!p[lp].trs[c];lp=p[lp].pre) p[lp].trs[c]=np; if(!lp)p[np].pre = 1; else lq = p[lp].trs[c]; if(p[lq].len==p[lp].len+1)p[np].pre = lq; else nq = ++tot; p[nq] = p[lq]; p[nq].len = p[lp].len+1; p[lq].pre = p[np].pre = nq; while(p[lp].trs[c]==lq) p[lp].trs[c] = nq; lp = p[lp].pre; las = np; void dfs(int u) if(u==1||vis[u])return ;vis[u]=1; v[u] = (p[u].cnt>=k)*(p[u].len-p[p[u].pre].len); dfs(p[u].pre); v[u]+=v[p[u].pre]; void build() for(int i=1;i<=n;i++) int u = 1; for(int j=ens[i-1]+1;j<=ens[i];j++) u = p[u].trs[sum[j]-‘a‘+1]; int tmp = u; while(tmp!=1&&use[tmp]<i) p[tmp].cnt++; use[tmp] = i; tmp = p[tmp].pre; for(int i=2;i<=tot;i++)dfs(i); sam; int main() scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%s",s+1); sam.res(); int len = strlen(s+1); for(int j=1;j<=len;j++) sam.insert(s[j]-‘a‘+1); sum[ens[i-1]+j]=s[j]; ens[i]=ens[i-1]+len; sam.build(); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) int u = 1; ll c = 0; for(int j=ens[i-1]+1;j<=ens[i];j++) u = p[u].trs[sum[j]-‘a‘+1]; c+=v[u]; printf("%lld ",c); printf(" "); return 0;
[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... 查看详情