时间限制：C/C++ 4秒，其他语言8秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format:%lld
题目描述
给定一个字符串，要求取出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
输出
2
说明
一种可行的方案：取出的三个子串分别为abc，ab，ab时，他们之间的位置并不相交且任意两个的最长公共前缀均为ab。
贼简单的一道题，很明显直接二分答案，用哈希来check是否有长度为k的字符串即可，check函数中用unordered_map节省时间，用类似滑动窗口的尺取操作来更新即可非常简单 然后就没什么好说的了
时间复杂度 O(nlogn)
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#include<unordered_map>
#define ls (p<<1)
#define rs (p<<1|1)
//#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=2000007;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
char s[N];
ll n,m,k,ans;
ll ha[N],p[N];
bool check(ll x)
{
unordered_map<ll,pair<ll,ll> >mp;
over(i,x,n)
{
ll tmp=ha[i]-ha[i-x]*p[x];
if(i-mp[tmp].first>=x)mp[tmp].first=i,mp[tmp].second++;
if(mp[tmp].second>=k)return true;
}
return false;
}
int main()
{
scanf("%lld%lld",&n,&k);
scanf("%s",s+1);
p[0]=1;
over(i,1,n)
{
p[i]=p[i-1]*2333;
ha[i]=ha[i-1]*2333+s[i];
}
int l=1,r=n/k;
while(l<=r)
{
ll mid=(l+r)/2;
if(check(mid))l=mid+1,ans=mid;
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧
京公网安备 11010502036488号