标签为 [字符串] 的文章

BZOJ3676 [Apio2014]回文串

题目传送门 先来考虑如何快速的求出一个子串的出现次数,那就建一个后缀自动机,预处理出每一个节点的|right(x)|,然后找到子串对应的节点就好了。但是如果从root开始转移的话太慢了,而且不好优化,所以可以尝试倒着来。在建sam的时候顺便记录s[1..x]所对应的节点,对于子串s[l..r],其所对应的节点一定是s[1..r]所对应的点在parent树上的祖先。所以可以倍增求出s[l..r]所对应的节点。 题目还有回文串这个限制,由manacher算法的推论可知一个字符串的本质不同的回文子串只有O(len)个,因为只有当右端点右移的时候的回文串才是之前 ......

BZOJ3926[Zjoi2015]诸神眷顾的幻想乡

题目传送门 看到题目描述的最后一句话,意思是这棵树最多只有20个叶子节点,这个限制很奇怪,也是本题的突破口。考虑任意一条链组成的字符串,不难发现都会被起点为某一个叶子的字符串包含。由于叶子节点的个数非常少,所以可以将以这些节点为起点的路径组成的字符串全部加入到一个广义后缀自动机里,然后就可以直接统计答案了。时间复杂度为O(20nc),可以轻松通过此题。 code: #include<bits/stdc++.h> using namespace std; int en,head[100005],Next[200005],vet[200005],degree[ ......

HDU 2594 Simpsons’ Hidden Talents

这道就是纯KMP,QAQ。 你只要把这两个字符串合在一起求一遍KMP就可以了 注意最后输出的总长度必须小于等于min(len1,len2). Code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char st[110000],st1[110000],st2[110000]; int s[110000]; int n,cnt,n1,n2; int main() { while (scanf("%s%s",st1+1,st2+1)!=EOF) { n1=strlen(st1+1); n2=strlen(st2+1); for (int i=2;i<=n1;i++) { int t=s[i-1]; while (t ......

HDU 2434 Period

继续切水题的我。 这道题算法KMP 然后你只需要在做KMP的时候看一下i%(i-next[i])是否等于0且next[i]不为0 如果是0说明这里有循环节(不信你可以自己模拟一下QAQ) Code: #include&lt;cstdio&gt; #include&lt;algorithm&gt; using namespace std; char st[1100000]; int s[1100000]; int n,cnt; int main() { scanf("%d",&amp;n); while (n) { cnt++; printf("Test case #%d\n",cnt); scanf("%s",st+1); for (int i=2;i&lt;=n ......

BZOJ 2434 阿狸的打字机

感觉最近只有我在写博客啊。 这道题的方法是AC自动机+dfs序+树状数组。 你扫描字符串,遇到‘P’就把当前节点设为危险节点,遇到‘B’就返回它的父亲,否则正常转移 于是一个AC自动机就建出来了。 然后你就是跑出以fail数组为连边的树的DFS 离线操作,将询问按y排序, 再次扫描字符串 如果为P,则求出y==当前P的次数的所在节点的子树大小。 如果为B,删去当前节点的影响,返回它的父亲 否则 加入,加上当前节点的影响 可以用树状数组维护 Code: #include<cstdio> #include<algorithm> #in ......

计蒜客 A String Game

题目传送门 这道题是那场比赛里唯一一道比较容易的题目,也是我唯一那道AC的题…… 由于要在si后加字母,而且要保持si为t的子串,这很明显要用到SAM。任何这题就变成了在一张DAG中的某些点上有若干棋子,每次操作要把其中一个棋子沿着DAG的边移动一格,不能操作者负。这就是一个非常裸的博弈论问题了,求出DAG上每个点的SG函数,然后对每个棋子所在的点的SG函数求异或和,如果结果为0则Bob获胜,否则Alice获胜。 code #include&lt;cstdio&gt; #include&lt;cmath&gt; #include&lt ......

对后缀自动机的一点认识

一个蒟蒻,在字符串方面只会Hash不会KMP,还有一点点AC自动机,竟然看起了SAM,真的很累。幸好有许多dalao的帮助(包括NBC),还有hihocoder上图文并茂的介绍,当然也有其他论文和博客,我竟然有一点点理(bei)解(xia)了SAM的代码。 对于一个字符串S,它对应的后缀自动机是一个最小的确定有限状态自动机(DFA),它接受且只接受S的后缀。 其实也能接受S的所有子串。 一些定义 endpos(s)即right(s):对于S中的一个字串s,endpos(s)是s在S中所有出现的结束位置的集合。且endpos()相同的字串属于同一种状态。 将子串重编号后: substr ......

BZOJ2555 SubString

题目传送门 solution: 增量构建后缀自动机,对于一个询问串ch,从S(S为初始状态)开始根据trans函数进行转移,ch是原串的一个子串当且仅当转移没有被丢弃。如果被丢弃了,那么答案显然是零,否则假设最后转移到了状态T,那么答案为|endpos(T)|。那么怎么统计每一个节点的|endpos()|呢?所有状态根据slink连边显然会形成是一棵树,不难发现一个节点u的|endpos()|等于其儿子的|endpos()|的和或者儿子的|endpos()|的和加一。那么怎么判断是否要加一?一个状态的|endpos()|为其儿子的|endpos()|和再加一的充要条件是这个状态包含一个 ......

后缀数组:从入门到不会

其实我也不是很会这种玄学的东西。。。 不过这东西貌似可以支持很多字符串操作。。。 求一个字符串中本质不同子串的数量  SPOJ Disubtr 先预处理出后缀数组,然后求出将后缀排完序后的相邻两个后缀的LCP, $Ans=\sum n-sa[i]-h[i]$ #include<bits/stdc++.h> using namespace std; char ch[1000000]; int x[1000000],y[1000000],sa[1000000]; int n,m,c[1000000],l,rank[1000000],h[1000000]; int main() { int cas; scanf("%d",&cas); while (cas--) { memset(c,0,siz ......

HihoCoder1036 AC自动机模板

这只是一份模板 AC自动机 code #include&lt;stdio.h&gt; #include&lt;cmath&gt; #include&lt;algorithm&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; using namespace std; int n,len,num,son[1000005][26],que[1000005],head,tail,hz[1000005],k1,k2; char st[1000005],st1[1000005]; bool flag[1000005],val[1000005]; int main(){ scanf("%d",&amp;n); num=1; for(int i=1;i&lt;=n;i++){ scanf("%s",st); ......