Fizzmy

z-box

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章 / z-box （共6篇）

Codeforces 126B Password- z-box算法

传送门题意：给出一个字符串，求不等于前后缀的最长的一段子串，使得这段子串即是前缀也是后缀 Solution: 这道题如果使用KMP解决并不这么直观使用z算法可以轻松地解决（如果没有学过z算法请点击这里）处理出z数组后，我们记录前i项的z的最大值对于第i+1项，如果z[i+1]...

2021-08-18

0 558

Codeforces 535D Tavas and Malekas-字符串匹配

传送门题意：给出文本串的长度n，给出模式串以及模式串在文本串中出现的位置，求有多少种文本串满足条件。 Solution: 在文本串中暴力加入模式串，最后判断匹配位置是否和给出的相符即可。代码（z-box赛高！）： #include<cstdio> #include<...

2021-08-18

0 519

Codeforces 631D Messenger-字符串匹配

传送门题意：给出两个分别为n,m项的字符串求第二个字符串在第一个中出现几次字符串按照 (li,ci) ( l i , c i ) 的形式给出 (如2-a 2-b 1-c 表示aabbc) n,m<=2e5 l<=1e6 n , m <= 2 e 5 l...

2021-08-18

0 365

Codeforces 149E Martian Strings-字符串匹配

传送门题意：给出一个长度为n的文本串和m个模式串，求有多少个模式串可以拆成两半，使得这两半按顺序匹配 (n<=2e5,m<=100) Solution：先正着跑一遍KMP,pos[i]表示模式串中最早能匹配到第i个字符的位置然后把文本串和模式串都取反，再跑一遍KMP，...

2021-08-18

0 454

Codeforces gym 100792B Banana Brain's Bracelet - z-box算法

传送门题意：给一个循环串A，和一个字符串C，求一个最长的A的子串B，使得将B首尾相接成一个循环串后，C是B的子串。 Solution：我们把A翻倍拼接，就可以消掉”A是循环串”z这个限制，发现C可以拆成一个前缀和一个后缀我们可以求出翻转前的z数组z1以及翻转后的z数组z2，分别表示...

2021-08-18

0 484

Codeforces 30E Tricky and Clever Password-字符串匹配

传送门题意：密码是一个长度为奇数的回文串，现在我们对这个密码进行加密：把密码分成 3 段，最前面的 X 个字符为一段，最后面的 X 个字符为一段，剩余的字符为一段。这三段依次称之为 prefix, suffix, middle 。middle 的长度为一个大于 0 的奇数， prefix 、...

2021-08-18

0 323