[ABC257G] Prefix Concatenation Solution

更好的阅读体验戳此进入

题面

给定仅存在小写英文字母的字符串 $S,T$$S, T$。你需要将 $T$$T$ 分割成 $k$$k$ 个 $S$$S$ 的前缀（或着说用 $S$$S$ 的若干个前缀组成 $T$$T$），最小化 $k$$k$，输出最小值。若 $k$$k$ 不存在输出 -1。

Solution

首先 $O(n^2)$$O(n^2)$ 的 DP 显然，我们记 $S(i,j),T(i,j)$$S(i, j), T(i, j)$ 为对应字符串 $[i,j]$$[i, j]$ 的子串，令 $dp(i)$$dp(i)$ 表示考虑 $T(1,i)$$T(1, i)$ 的最小 $k$$k$。易得转移：

不难发现这个 $\mathtt{\text{1D1D}}$$\texttt{1D1D}$ 的 DP 是 $O(n^2)$$O(n^2)$ 的无法通过，考虑优化。

首先有一个思路，已知 $dp(i)$$dp(i)$ 单调不降，证明显然，考虑若 $dp(i)>dp(i+1)$$dp(i) \gt dp(i + 1)$，那么在 $dp(i+1)$$dp(i + 1)$ 的方案中将最后一部分去掉第 $i+1$$i + 1$ 个一定可以变为 $dp(i)$$dp(i)$ 且 $k$$k$ 不劣，得证。

然后根据这个思路我们每次转移只需要找到最小的合法 $j$$j$ 转移即可，可以通过 KMP 中的 next 数组维护。

具体地，不难发现我们这个东西求的可以转化为求 border，具体地，我们将 $S$$S$ 后追加一个占位符，然后再连接上 $T$$T$，记 P = S + '#' + T，这样我们对 $P$$P$ 跑一遍 KMP 的建立 next 数组过程，不难发现对于转移 $i$$i$ 时需要的 $j$$j$，即为 $i-nxt(le{n}_S+1+i)$$i - nxt(len_S + 1 + i)$，这里的 $+1$$+1$ 即为我们添加的占位符 #。

最终 DP 优化为 $\mathtt{\text{1D0D}}$$\texttt{1D0D}$，复杂度 $O(n)$$O(n)$，可以通过。

同时还有一种方法，发现修改状态为后缀可以支持逆序转移，于是转移变为：

此时发现每次可以转移的 $j$$j$ 是连续的，对应 $S$$S$ 和 $T(i,le{n}_T)$$T(i, len_T)$ 的 LCP，于是可以通过哈希 + 二分处理每次转移的 LCP 长度，然后线段树优化 DP 即可，最终复杂度 $O(n\log n)$$O(n \log n)$，劣于正向转移但也可以通过，且思路更直观，仅代码实现略长。

Code

xxxxxxxxxx
61
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
string S, T;
26
char s[1100000];
27
int dp[1100000];
28
int nxt[1100000];
29

30
int main(){
31
    memset(dp, 0x3f, sizeof dp);
32
    cin >> S >> T;
33
    sprintf(s + 1, "%s#%s", S.c_str(), T.c_str());
34
    int lenS = S.length(), lenT = T.length();
35
    dp[lenS + 1] = 0;
36
    int cur(0);
37
    for(int i = 2; i <= lenS + lenT + 1; ++i){
38
        while(cur && s[cur + 1] != s[i])cur = nxt[cur];
39
        if(s[cur + 1] == s[i])++cur;
40
        if(i > lenS + 1)dp[i] = dp[i - cur] + 1;
41
        nxt[i] = cur;
42
    }printf("%d\n", dp[lenS + lenT + 1] < 0x3f3f3f3f ? dp[lenS + lenT + 1] : -1);
43
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44
    return 0;
45
}
46

47
template < typename T >
48
inline T read(void){
49
    T ret(0);
50
    int flag(1);
51
    char c = getchar();
52
    while(c != '-' && !isdigit(c))c = getchar();
53
    if(c == '-')flag = -1, c = getchar();
54
    while(isdigit(c)){
55
        ret *= 10;
56
        ret += int(c - '0');
57
        c = getchar();
58
    }
59
    ret *= flag;
60
    return ret;
61
}

UPD

update-2022_12_09 初稿