CF822E Liar 题解

题意：

给定两个字符串 \(s, t\)，长度分别为 \(n, m\)。你需要选择 \(s\) 的若干个两两不相交的子串，然后将它们按照原先在 \(s\) 中出现的顺序合并起来，希望得到 \(t\)。

令 \(f(s, t)\) 表示要选择的 \(s\) 的子串数目的最小值，以便它们的并是串 \(t\)。如果无法合理选择这样的子串，则 \(f(s, t) = +\infty\)。现在 cxy 想知道，对于给定的 \(s, t\)，是否有 \(f(s, t) \leq x\)。

输入格式：

第一行包含一个正整数 \(n,~(n \leq 10^5)\)，表示字符串 \(s\) 的长度。

第二行为一个长度为 \(n\) 的，只包含小写字母 \(\mathtt{a} \sim \mathtt{z}\) 的字符串 \(s\)。

第三行包含一个正整数 \(m,~(m \leq n)\)，表示字符串 \(t\) 的长度。

第四行类似地包含一个长度为 \(m\) 的字符串 \(t\)。

第五行包含一个正整数 \(x,~(x \le 30)\)，表示最大能分成的断数 (即上文不等式中的 \(x\))。

输出格式：

仅输出一行，包含一个字符串，输出 YES 如果 \(f(s, t) \leq x\)，否则输出 NO。

吐了，以为会被卡单哈，写了2&3哈希，最后反而被卡常了

然后这个二分边界什么的东西搞得我要吐了（主要我看的题解是从 \(0\) 开始的）

下文中使用 \(a\uparrow b+c\) 表示 \(a \leftarrow \max\{a,b+c\}\)

设 \(f_{i,j}\) 表示考虑字符串 \(s\) 的前 \(i\) 个字符，取出不超过 \(j\) 段，能拼出 \(t\) 的前缀的最大长度。

考虑转移。第一种，不管第 \(i+1\) 个字符 \[ f_{i+1,j} \uparrow f_{i,j} \] 第二种，拼接一个 \(s[i+1\dots i+k]=t[j+1\dots j+k]\) ，且 \(k\) 尽可能的大。

不难发现， \(k\) 就是 \(s[i+1\dots n]\) 和 \(t[j+1\dots m]\) 的LCP（最长公共前缀）

这里其实利用了贪心的思想，正确性显然。

这个可以用二分加hash求出来 \[ f_{i+k,j} \uparrow f_{i,j} + k \] 然后看一下是否存在一个 \(j\) 使得 \(f_{n,j}=m\) ，即可判断是否有解了。

时间复杂度 \(O(nk \log n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))
#define K 35
#define C 1
const int Base[] = {127};
const int Mod[] = {1000000033};
void up(int &x,int y) { x < y ? x = y : 0;}
char s[N],t[N];
int n,m,k,f[N][K],hsh1[C][N],hsh2[C][N],pwd[C][N];
void make_hash()
{
    for(int i=0; i<C; i++)
    {
        pwd[i][0] = 1;
        hsh1[i][0] = hsh2[i][0] = 0;
    }
    int l = max(n,m);
    for(int id=0; id<C; id++)
        for(int i=1; i<=l; i++)
        {
            pwd[id][i] = pwd[id][i-1] * Base[id] % Mod[id];
            hsh1[id][i] = (hsh1[id][i-1] * Base[id] + s[i] - 'a') % Mod[id];
            hsh2[id][i] = (hsh2[id][i-1] * Base[id] + t[i] - 'a') % Mod[id];
        }
}
int gethash(int (*h)[N],int id,int l,int r)
{
    int t=(h[id][r] - h[id][l-1] * pwd[id][r-l+1] % Mod[id]) % Mod[id];
    t = (t + Mod[id]) % Mod[id];
    return t;
}
bool work(int x,int y,int len)
{
    for(int id=0; id<C; id++)
        if(gethash(hsh1,id,x,x+len-1) != gethash(hsh2,id,y,y+len-1))
            return 0;
    return 1;
}
int LCP(int x,int y)
{
    if(s[x] != t[y]) return 0;
    int l=1, r = min(n-x+1, m-y+1);
    while(l < r)
    {
        int mid = (l+r+1) >> 1;
        work(x,y,mid) ? l=mid : r=mid-1;
    }
    return l;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (s+1) >> m >> (t+1) >> k;
    make_hash();
    int now,lcp;
    for(int i=0; i<n; i++)
        for(int j=0; j<=k; j++)
        {
            up(f[i+1][j], now=f[i][j]);
            if(now < m && (lcp = LCP(i+1,now+1)))
                up(f[i+lcp][j+1], now + lcp);
        }
    bool ok=0;
    for(int i=0; i<=k; i++) ok |= (f[n][i] == m);
    cout << (ok ? "YES" : "NO") << '\n';
    return 0;
}