题目描述
将字符串 \(T\) 拆成若干个子串，使这些子串为字符串 \(S\) 的前缀，要求拆分形成的子串数最小。
思路整理
实际上并不需要倒着枚举，也不需要线段树，更不需要 Z 函数。
如果你做过 P3002 恐吓信 这道题，不难发现他们之间的相似之处。
首先我们容易想到一个 \(O(n^2)\) 的暴力 dp 。令 \(f[i]\) 为切完前 \(i\) 个字符形成的最小子串，则可以列出下列转移方程：
\[f[i] = min(f[i-j]) + 1(0<=j<=min(|T|,i)\; and \; T(1 \sim j) == S[(i-j+1) \sim i]) \]转移方程的实际含义就是枚举最后一刀应该砍在哪里，才能使最后一个子串为 \(T\) 的前缀，很简洁，我们尝试优化她。
首先方程的枚举只用于求最小的满足条件的 \(f[j]\) 。这很浪费。我们可以输出 \(f\) 数组进行观察，然后可以发现 \(f\) 数组单调递增。
证明一下：因为 \(S[1 \sim (i-1)]\) 是 \(S[1 \sim i]\) 的前缀，所以必然有这么长一种策略：在找到 \(S[1 \sim i]\) 的最后一个 \(T\) 的前缀时，将前缀的最后一个字母去除，就变成了\(S[1 \sim (i-1)]\) 的最后一个 \(T\) 的前缀。因此 \(f[i-1] <= f[i]\) 。
这样，我们的任务就变成了：寻找最小的满足条件的 \(j\) 。
在 P3002 中，我们的任务与这题类似。只不过 \(T\) 的所有子串都可作为魔法词缀。所以，在那题里，我们使用了后缀数组进行优化。
回到这题， 模拟一下找最远位置的步骤，发现我们要找的是最大的数 \(i\) 使 \(T\) 的长度为 \(i\) 前缀与 \(S\) 长度为 \(i\) 的后缀相等。
不如把这个问题视作将 \(T\) 在 \(S\) 上匹配。将 \(T\) 从第一位开始一位一位跟 \(S\) 的最后的字符匹配，这时我们可以发现这就是模拟了 KMP 文本串匹配模式串的过程。
从反方向理解一下：当 KMP 匹配到第 \(i\) 位时，指针 \(j\) 表示模式串匹配到前 \(j\) 位了。而与之匹配的就是文本串的后缀。
于是我们可以用 KMP 优化，在匹配途中记录下每个 \(i\) 对应的指针 \(j\) 作为能匹配的最大前缀，转移时只需要从这个转移即可。时间复杂度 \(O(|T|+|S|)\) ，瓶颈在 KMP。
代码讲解
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e7 + 5;
int n, m;
string T, S;
int dp[maxn], qian[maxn], f[maxn];
void kmp()
{
int j=0;
for(int i=2;i<=n;i++){
while(j&&T[j+1]!=T[i]) j=qian[j];
if(T[j+1]==T[i]) j++;
qian[i]=j;
}
j=0;
for(int i=1;i<=m;i++){
while(j&&T[j+1]!=S[i]) j=qian[j];
if(T[j+1]==S[i]) j++;
f[i] = j;
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> T >> S;
T = ' ' + T;
S = ' ' + S;
for(int i = 1;i <= m;i ++) dp[i] = 19198100;
dp[0] = 0;
kmp();
for(int i = 1;i <= m;i ++)
{
dp[i] = min(dp[i], dp[i - f[i]] + 1);
}
if(dp[m] == 1919810) cout << "Fake" << endl;
else cout << dp[m] << endl;
return 0;
}
后记
本来不写题解不觉得，一写题解发现很多细节做题时并没有考虑清楚，例如单调性的证明做题时是通过打表得出的。这也证明了写题解和解题报告也是做题提升的重要一环。
标签：子串,匹配,前缀,int,P8112,KMP,破译,maxn,符文 From： https://www.cnblogs.com/closureshop/p/16860518.html