相似的子串

[编程题]相似的子串

时间限制：C/C++ 4秒，其他语言8秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串，要求取出k个位置不相交的子串，且他们之间任意两个的最长公共前缀的长度均不小于x。现在给出k，求最大的x。

两个字符串str1，str2的公共前缀为x指str1和str2的长度均不小于x且这两个字符串的前x个字符对应相同。最长公共前缀即所有的公共前缀里最长的那个，如没有公共前缀则视为最长公共前缀长度为0。

输入描述:

第一行两个正整数n，k（2≤n≤200000，2≤k≤n）。第二行一个长度为n的仅包含小写英文字母的字符串。

输出描述:

仅一行一个整数x代表答案。

示例1

输入

7 3 
abcabab

输出

说明

一种可行的方案：取出的三个子串分别为abc，ab，ab时，他们之间的位置并不相交且任意两个的最长公共前缀均为ab。

算法知识视频讲解

Lskkkno1

发表于 2020-04-10 22:00:56

相似的子串题目描述给定一个字符串，询问出现次数大于等于的最长子串的长度（子串不相交）。正解二分 + 哈希。首先答案显然满足单调性。二分长度后，如何判断答案可行？设表示以为开头，长度为的子串，到为止，在不相交的情况下，最多出现了多少次。更新数组的时候有个比展开全文

WuliWuliiii

发表于 2020-04-11 09:39:01

求K个不相交字符子串的最大相同前缀长度x。很容易往后缀数组上靠，但是这还不够，因为很容易就想偏了，这里，我们想处理一个是不重叠，一个是最大的前缀相同，于是，不妨设最长前缀为x，然后二分这个x，这是因为height的关系具有连续性，所以这样就能很清晰的划分出来我们需要进行处理的sa的区间了。展开全文

Meul

发表于 2020-04-12 18:14:18

NC5026E 题意把原题意转化为给你一个长为的字符串，求至少有个相同且不相交的长为(可为)的子串，为多少？思路二分+哈希字符串时间复杂度这道题不要求得到所求子串为什么，而要求子串所能取得最大长度，且答案具有严格单调性，故可以二分答案。那么如何验证？首先预处理字符串Hash得到Hash数组表展开全文