分类: [字符串]

bzoj 3238 差异

题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=3238 后缀数组+单调队列 这是一道后缀数组的模板题。 简单来说,就是先用后缀数组求出h数组。 然后利用单调队列在o(n)的时间复杂度下求出任意两个后缀的最大公共前缀长度的和。 大家看代码理解吧。 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long ans; char st[510000]; int sum[510000],c[510000],h[510000],sa[2][510000],rk[2][510000]; in ......

回文自动机

回文自动机Palindromic Automaton(又称回文树Palindromic Tree,简称pam)能干什么? 对于字符串S[1..n],比如它可以求出S的所有本质不同的回文子串,并求出每一个本质不同的子串在S中出现的次数,当然还能干别的很多事情。 现在来看回文自动机是如何构建的。 定义变量: cnt表示pam中的节点数,pam的每一个节点分别表示一个本质不同的回文串子串 trans[u][c]表示在节点u所对应的回文子串两边加入字符c时变成的回文串对应的节点(可能不存在) len[u]表示节点u表示的回文子串的长度 fail[u]表示结尾与u表示的回文子串相同,长度小 ......

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 3746 Cyclic Nacklace

我能表示自己不会做吗。 好吧。 其实这道题就是个裸的KMP 但我一开始竟然没有看出来 显而易见的是,如果要添加几个字符的话,肯定是字符串的循环节缺了一部分 所以答案是 (n-fail[n])-n%(n-fail[n]) Code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char st[210000]; int n; int s[210000]; int main() { int T; scanf("%d",&T); while (T--) { scanf("%s",st+1); n=st ......

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 ......

BZOJ 2746 旅行问题

这是一道AC自动机QAQ. 题意是求任意两个字符串前缀的最大公共后缀,并且这个后缀要在一个字符串里出现过,输出这个后缀转化成十进制后的答案。 显而易见的是,先建个AC自动机,然后求出fail数组。 你的问题其实就是求两个字符串前缀所在的节点的LCA,然后输出根到它路径上所形成的字符串即可(这个可以预处理)   Code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MOD=1e9+7; int pos[2100000],dep[1100000],q[1100000], ......

BZOJ 1009 GT考试

这道可以用KMP 很显然又是一个模板题 只不过因为n太大了,于是用了矩阵乘法 你只要先预处理出fail数组, 然后转移矩阵也就可以求出来了, 你只需要枚举每个前缀的转移,假设枚举前缀i,有一个转移是j,你就在g[i][j]上+1 不过注意如果转移为m的话就continue 代码还是很短。 Code: #include<cstdio> #include<algorithm> using namespace std; int n,m,MOD; char st[22]; int s[22]; long long f[22][22],df[22][22],dg[22][22],dgg[22][22],g[22][22]; int main() { scan ......