首页 > 相似的子串
开通博客写题解
头像 Lskkkno1
发表于 2020-04-10 22:00:56
相似的子串 题目描述 给定一个字符串，询问出现次数大于等于 的最长子串的长度（子串不相交）。 正解 二分 + 哈希。 首先答案显然满足单调性。 二分长度 后，如何判断答案可行？ 设 表示以 为开头，长度为 的子串，到 为止，在不相交的情况下，最多出现了多少次。 更新 数组的时候有个比 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 WuliWuliiii
发表于 2020-04-11 09:39:01
求K个不相交字符子串的最大相同前缀长度x。 很容易往后缀数组上靠，但是这还不够，因为很容易就想偏了，这里，我们想处理一个是不重叠，一个是最大的前缀相同，于是，不妨设最长前缀为x，然后二分这个x，这是因为height的关系具有连续性，所以这样就能很清晰的划分出来我们需要进行处理的sa的区间了。 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 Meul
发表于 2020-04-12 18:14:18
NC5026E 题意 把原题意转化为给你一个长为的字符串，求至少有个相同且不相交的长为(可为)的子串，为多少？ 思路 二分+哈希字符串 时间复杂度这道题不要求得到所求子串为什么，而要求子串所能取得最大长度，且答案具有严格单调性，故可以二分答案。那么如何验证？首先预处理字符串Hash得到Hash数组表 展开全文
去ta的博客 赞 (1) 回复(-1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”