bzoj3277串

关键词：

Description

Input

Output

Sample Input

Sample Output

HINT

Source

广义后缀自动机

把所有串建成广义后缀自动机，开一个size数组记录每个结点被多少个串经过。

若一个结点x的size>=k，则它有maxlen[x]-maxlen[fa[x]]（即right集合大小）个贡献，否则贡献为0

从自动机root开始DFS一遍，累计每个点的贡献。

对于每个串，用它在自动机上跑一遍，累计所有经过的点的贡献，即是答案。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<vector>
  7 #define LL long long
  8 using namespace std;
  9 const int mxn=200011;
 10 int read(){
 11     int x=0,f=1;char ch=getchar();
 12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
 13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
 14     return x*f;
 15 }
 16 struct edge{
 17     int v,nxt;
 18 }e[mxn<<1];
 19 int hd[mxn],mct=0;
 20 void add_edge(int u,int v){
 21     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;
 22     return;
 23 }
 24 vector<int>ve[mxn>>1];
 25 int n,K;
 26 int id;
 27 struct SAM{
 28     int t[mxn][26];
 29     int fa[mxn],mx[mxn];LL sz[mxn];
 30     int w[mxn],rk[mxn];
 31     int nxt[mxn];
 32     int S,last,cnt;
 33     void init(){S=last=cnt=1;return;}
 34     void add(int c){
 35 //      printf("add:%d
",c);
 36         int np=++cnt,p=last;last=np;
 37         mx[np]=mx[p]+1;
 38         for(;p && !t[p][c];p=fa[p])t[p][c]=np;
 39         if(!p){fa[np]=S;}
 40         else{
 41             int q=t[p][c];
 42             if(mx[q]==mx[p]+1)fa[np]=q;
 43             else{
 44                 int nq=++cnt;mx[nq]=mx[p]+1;
 45                 memcpy(t[nq],t[q],sizeof t[q]);
 46                 sz[nq]=sz[q];nxt[nq]=nxt[q];
 47                 fa[nq]=fa[q];
 48                 fa[q]=fa[np]=nq;
 49                 for(;p && t[p][c]==q;p=fa[p])t[p][c]=nq;
 50             }
 51         }
 52         ve[id].push_back(np);
 53         while(np){
 54             if(nxt[np]!=id){++sz[np];nxt[np]=id;np=fa[np];}
 55             else break;
 56         }
 57         return;
 58     }
 59     void ST(){
 60         for(int i=1;i<=cnt;i++)++w[mx[i]];
 61         for(int i=1;i<=cnt;i++)w[i]+=w[i-1];
 62         for(int i=cnt;i;i--)rk[w[mx[i]]--]=i;
 63         for(int i=1;i<=cnt;i++){
 64             int r=rk[i];
 65             add_edge(fa[r],r);
 66             sz[r]=(sz[r]>=K)?mx[r]-mx[fa[r]]:0;
 67         }
 68         return;
 69     }
 70     void DFS(int u){
 71         sz[u]+=sz[fa[u]];
 72         for(int i=hd[u];i;i=e[i].nxt)
 73             DFS(e[i].v);
 74         return;
 75     }
 76 }sa;
 77 char s[mxn];
 78 int main(){
 79     int i,j;
 80     n=read();K=read();
 81     sa.init();
 82     for(i=1;i<=n;i++){
 83         scanf("%s",s+1);
 84         int len=strlen(s+1);
 85         id=i;
 86         for(j=1;j<=len;j++)sa.add(s[j]-‘a‘);
 87         sa.last=sa.S;
 88     }
 89     sa.ST();
 90     sa.DFS(1);
 91     sa.sz[sa.S]=0;
 92     LL ans=0;
 93     for(i=1;i<=n;i++){
 94         ans=0;int ed=ve[i].size();
 95         for(j=0;j<ed;j++){
 96             ans+=sa.sz[ve[i][j]];
 97         }
 98         printf("%lld ",ans);
 99     }
100     return 0;
101 }
102 

bzoj3277:串

Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。Solution出现\(k\)次的问题比较好解决,我们构出\(parent\)树,然后在上... 查看详情

bzoj3277:串(代码片段)

以下全部是笔记，不要看了注意：要求的不是"有多少不同的子串是..."，相同的要重复计算贡献。例如：32acaac答案是311第一个串中两个a都出现了两次，c出现了两次，所以第一个的答案是3广义后缀自动机模板。各个串连起来中间... 查看详情

[bzoj3277]串广义后缀自动机(代码片段)

3277:串TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 811  Solved: 329[Submit][Status][Discuss]Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k... 查看详情

bzoj3473字符串&bzoj3277串

题意：给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串.注意本质相同的子串多次出现算多次,如11aaa这组数据答案为6,贡献1WA.代码里有些部分是为了处理子串本质不同,可能没删... 查看详情

并不对劲的bzoj3277

陈年老坑题意大概是有n个字符串，要求出每一个字符串的所有子串（不包括空串）在所有字符串（包括自身）中出现次数不少于k的有多少个。n,k,字符串总长<=100000。如果只有一个串的话，非常好办，直接把它建成后缀自动机... 查看详情

bzoj3277&bzoj3473串——广义后缀自动机(代码片段)

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3277https://www.lydsy.com/JudgeOnline/problem.php?id=3473广义后缀自动机：https://www.cnblogs.com/HocRiser/p/9580478.html像Trie树一样处理了重复节点；基数排序后DP，f数组求的直接是这个点及其祖先的答案... 查看详情

bzoj3277串(代码片段)

题目描述题解：对于多串的子串，我们可以建出广义后缀自动机。由于本题询问的是（子串出现次数>=k）×len的总和，就将所有串扔到自动机中，爆跳pre并标记。每个点得到一个经过次数cnt。若cnt>=k，说明这个点压缩的所有... 查看详情

bzoj3277:串(代码片段)

Description字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。Input第一行两个整数n，k。接下来n行每行一个字符串。n,k,l<=10000... 查看详情

bzoj3676apio2014回文串

题目链接：回文串　　我终于也会回文自动机辣！　　其实吗……我觉得回文自动机(听说这玩意儿叫(PAM))还是比较(simple)的……至少比(SAM)友善多了……　　所谓回文自动机，每个节点就代表一个回文串。回文自动机的每个节点... 查看详情

bzoj4502:串

4502:串TimeLimit:30Sec  MemoryLimit:512MBSubmit:245  Solved:123[Submit][Status][Discuss]Description兔子们在玩字符串的游戏。首先，它们拿出了一个字符串集合S，然后它们定义一个字符串为“好”的，当且仅当它可以被分成非空... 查看详情

[bzoj2555]substring

bzoj题意给你一个初始模板串，要求资瓷以下两个操作：1、在模板串的末尾接上一个串；2、查询一个串在模板串中出现了多少次。强制在线。sol末尾添加直接\(extend\)。查询一个串的出现次数就是查对应状态的\(right\)集合大小。... 查看详情

bzoj4503两个串(代码片段)

题目描述：给一个文本串和一个模式串，模式串中有通配符$‘?‘$，问匹配多少次，哪里可以匹配。题解：极为暴力，$FFT$单字符匹配$26$次，总计$26*3=78$次$FFT$。其实有更好的方法我放在下一篇博客里代码：#include<cmath>#includ... 查看详情

bzoj1396识别子串

http://www.lydsy.com/JudgeOnline/problem.php?id=1396 (题目链接)题意　　问字符串S每一位的最短识别子串是多长(识别子串指包含这个字符且只出现在S中一次的子串)。Solution　　很简单，搞出后缀数组以后，对于每一个后缀i，都可以求... 查看详情

bzoj4503两个串

TimeLimit: 20Sec  MemoryLimit: 256MBSubmit: 398  Solved: 190Description兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，分别在哪些位置出现。注意T中可能有“?”字符，这个... 查看详情

bzoj2946:[poi2000]公共串

Description最长公共子串,(nleqslant5,lleqslant1000)SolutionSAM...对于同一字符串取max，不用字符串取minCode/**************************************************************Problem:2946User:BeiYuLanguage:C++Result:AcceptedT 查看详情

bzoj2320:最多重复子串

2320:最多重复子串TimeLimit: 40Sec  MemoryLimit: 128MBSubmit: 246  Solved: 66[Submit][Status][Discuss]Description一个字符串P的重复数定义为最大的整数R，使得P可以分为R段连续且相同的子串。比方说，“ababab”的重复数 查看详情

[bzoj4503]两个串

$\newcommandalign[1]\beginalign*#1\endalign*$如果$S_i\cdotsi+m-1$与$T$相等，那么$\align\sum\limits_j=0^m-1\left(S_i+j-T_j\right)^2T_j=0$（令通配符为$T_i=0$），展开得到$\align\sum\limits_j=0^m-1S^2_ 查看详情

bzoj4502:串

题意：给定一个由n个串组成的集合（n<=10000,len<=30），求组成不同好串的方案数。其中好串的定义为：可被分割成两个非空串且分别对应原集合中两个串（可相同）的前缀。首先直接弄肯定不行，会算重。所以要么除掉相同... 查看详情