大家好，这里是牛客周赛 Round 56 的组题人。希望大家喜欢这一场的题目~
从组题人的角度来总体评价这一场，
打卡；
需要理解一下题意的打卡，注意加粗字体的小骗局；
构造+思维+位运算，可能大家对位运算不是很熟悉，但其实思维难度低于 ；
在校招中，位运算是考察较为频繁的知识点，需要大
展开全文
这道题好难喵！给猫猫做傻了喵！借用了蒟蒻果冻01大佬的O(n) 思想，仅仅只是为了让更多人和猫猫一样理解他的思想喵！猫猫解释时间到！(≧▽≦)第一步：看看 t 的开头有几个相同的小可爱设定一个 z 来统计 t 开头有多少个连续相同的字符
int z = 1;
while (z + 1 < n
展开全文
这里直接利用z函数的信息复用思想，可以达到最优的时间复杂度.发现可以先得到从每个开始的和的后缀的LCP的长度，记为数组 b.难点是得到翻转后与的LCP的长度，记为数组 a： 设已经得到，此时和的末尾分别加上一个和，如果，那么显然的；否则设与的LCP的长度为，如果，那么与的LCP的长度小于，也
展开全文
这有 2200？？？
注意到操作是平凡的，我们直接维护整个串的翻转，那么操作就可以简单表示，又因为 lcp 是具有单调性的，考虑二分。于是对于每个 ，我们可以二分 lcp 的值，然后对于每个二分出来的值，假设当前在处理 的答案，二分的答案是 ，如果 ，说明这一段全都是需要翻转的，直接处理。如果 ，
展开全文
思路
二分 + 字符串哈希
对于每次翻转，二分lcp即可，check函数通过字符串哈希进行哈希值快速获取，然后判断即可。
代码
# 字符串哈希
base, mod = 1331, 10**9 + 7
base_inv = pow(base,mod-2,mod)
def getPreHash(s):
展开全文
题目链接
不是烤串故事
题目描述
给定两个长度为 的字符串 和 。对于每一个 ，我们通过翻转 的前 个字符得到一个新的字符串 。任务是找到所有 中，使得 和 的最长公共前缀 (LCP) 最长的那个，并输出这个最长的 LCP 长度以及达到该长度的最小的 。
解题思路
这是一个可以通过字符
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
