牛客练习赛61 E-相似的子串（hash+二分）

链接：https://ac.nowcoder.com/acm/contest/5026/E
来源：牛客网

题目描述

给定一个字符串，要求取出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。

思路：

取出k个位置不相交的子串，且他们之间任意两个的最长公共前缀的长度均不小于x。

可以把每一个子串的最长公共前缀之后的字符都删除掉，并没有任何影响。

问题转化为：

要求取出k个位置长度为x的不相交的相等的子串，切x最大。

把问题转化成验证型问题：

判断是否存在k个不相交的长度为mid的相等子串。

很显然 $mid$ 具有二分性，区间为 $[0,n/k]$ ，

判断方法：

$map<ull, int> last[i]$ 代表hash值为 $\mathit i$ 的字符串的最近一次出现时的首字符位置。

$f[i]$ 代表以 $s[i]$ 为首字符长度为 $mid$ 的字符串已经出现的次数。

当 $i - mid > 0$ 时将 $i - mid$ 首字符长度为 $mid$ 的字符串的 $last$ 更新，从而解决子串不相交。

维护 $res$ 作为 $f[i]$ 的最大值，判断 $k \leq res$ 即可知道长度 $mid$ 是否满足条件。

注意：

虽然二分区间为 $[0,n/k]$ ，但是代码中的check区间应该为 $[1,n/k]$ ，并将 $ans$ 的初始值设为 $0$ ，可以避免 $mid=0$ 给check带来的麻烦，另外有一个方法是，check函数中对 $mid=0$ 的情况特判返回 $true$ 。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x)  if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
char s[maxn];
int n;
int k;
typedef unsigned long long ull;
ull base = 127;
ull pw[maxn];
ull a[maxn];
void hash_pre()
{
    a[0] = 0;
    pw[0] = 1;
    repd(i, 1, n)
    {
        a[i] = a[i - 1] * base + (s[i] - 'a');
        pw[i] = pw[i - 1] * base;
    }
}
ull get(int l, int r)
{
    return (a[r] - pw[r - l + 1] * a[l - 1]);
}

unordered_map<ull, int> last;
int f[maxn];
bool check(int x)
{
    int res = 0;
    f[0] = 0;
    repd(i, 1, n)
    {
        if (i - x > 0)
        {
            last[get(i - x, i - 1)] = i - x;
        }
        f[i] = f[last[get(i, i + x - 1)]] + 1;
        res = max(res, f[i]);
        if (res >= k)
            break;
    }
    last.clear();
    return res >= k;
}
int main()
{
#if DEBUG_Switch
    freopen("C:\\code\\input.txt", "r", stdin);
#endif
    //freopen("C:\\code\\output.txt","r",stdin);
    n = readint(); k = readint();
    scanf("%s", s + 1);
    hash_pre();
    int l = 1;
    int r = n / k;
    int mid;
    int ans = 0;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid))
        {
            l = mid + 1;
            ans = mid;
        } else
        {
            r = mid - 1;
        }
    }
    printf("%d\n", ans );
    return 0;
}