[数据结构与算法]洛谷PP2031 脑力达人之分割字串【字符串DP】【黄】

Date：2022.03.16
题目描述
现在有一个字符串，你可以对这个字符串进行拆分，如 abcvsdaas 可以拆分为 abc|vs|d|aas，现在再给你一个字典，要求分割成的每一个子串必须要有包含其中的任意一个单词。那么最多可以分为几个子串呢？
输入格式
第一行，一行字符串
第二行一个正整数 N，表示字典中字符串的数量
接下来 N 行，每行一个字符串 Ai，表示字典中的一个字符串。
输出格式
一个整数，表示最多的分割数。
输入输出样例
输入 #1复制
asdsd
3
as
sd
ds
输出 #1复制
2
说明/提示
特殊情况：
如果原字符串不能被分割，请输出 0。
数据范围：
对于 20% 的数据，1≤∣s∣≤50,1≤n≤50。
对于 100% 的数据，1≤∣Ai∣≤∣s∣≤300，1≤N≤500。
其中，|s|,|Ai| 表示字符串 s 与 Ai 的长度。

思路①：问题即求出给定串最多包含几个子串，子串是可重复的（例：abab是两个ab），但不可交叉（例：abs，其中不能认定为含ab和bs两个子串）。
$f[i]:$以$i$为结尾的串最多可分出几个子串。
设第$j$个子串为$zc[j]$状态转移方程：$f[i]=max(f[i],f[i?zc[j].length()]+1)$
$【zc[j]==s.substr(i?zc[j].length()+1,i)\wedge i>=zc[j].length()】$
核心思想：每次找看当前子串是否可作为以$i$结尾的后缀。
代码如下：

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
const LL N = 1010,INF=0x3f3f3f3f3f3f3f3f;
typedef pair<LL, LL> PII;
LL t,n,m,k,f[N];
string zc[N];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string ss;cin>>ss;
    string s=" ";s+=ss;
    cin>>n;f[0]=0;
    for(int i=1;i<=n;i++) cin>>zc[i];
    for(int i=1;i<=ss.length();i++)
        for(int j=1;j<=n;j++)
            if(i>=zc[j].length())
            {
                //cout<<zc[j]<<' '<<s.substr(i-zc[j].length()+1,i)<<endl;
                if(zc[j]==s.substr(i-zc[j].length()+1),i)
                    f[i]=max(f[i],f[i-zc[j].length()]+1);
            }
    LL maxx=0;
    for(int i=1;i<ss.length();i++) maxx=max(maxx,f[i]);//找到不同结尾但是最大的
    cout<<maxx;
    return 0;
}

全wa。
思路②：思路①漏了一个非常重要的限制！！！每次判断时$zc[j]$的结尾不非是第$i$个字符！！！$zc[j]$也可以以$i?1、...、zc[j].length()$作为结尾，即要考虑$f[zc[j].length(),i?zc[j].length()]$来更新$f[i]$；而思路①显然只考虑了以$f[i?zc[j].length()]$来更新$f[i]$！！！
代码如下：（思路一样，方向反着的）

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
const LL N = 2e6+10,INF=0x3f3f3f3f3f3f3f3f;
typedef pair<LL, LL> PII;
LL t,n,m,k,f[N];
string zc[N];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string ss;cin>>ss;
    string s=" ";s+=ss;
    cin>>n;f[0]=0;
    for(int i=1;i<=n;i++) cin>>zc[i];
    for(int i=0;i<=ss.length();i++)
        for(int j=1;j<=n;j++)
            if(ss.length()-i>=zc[j].length() && zc[j]==s.substr(i+1,zc[j].length()))
            {
                for(int k=i+zc[j].length();k<=ss.length();k++)
                    f[k]=max(f[k],f[i]+1);
            }
    cout<<f[ss.length()];
    return 0;
}