#include <bits/stdc++.h>
using namespace std ;
set<string> P[15] ;
string s, z ; 
bool dp[200005] ;
int len, m = 0, ans = 0 ;
int main()
{
	std::ios::sync_with_stdio(false) ;
	std::cin.tie(0) ;
	while(cin >> s)
	{
		if(s[0] == '.') break ;
		len = s.length() ;
		P[len].insert(s) ;
		m = max(m, len) ;
	}
	z = " " ;
	while(cin >> s) z = z + s ;
	len = z.length() ;
	dp[0] = 1 ;
	for(int i = 1; i < len; i ++)//此处为小于 
	{
		for(int j = min(i, m); j >= 1; j --)
		{
			s = z.substr(i - j + 1, j) ;
			if(P[s.length()].count(s) && dp[i - j])
			{
				dp[i] = 1 ;
				ans = i ;
			}
		}
	}
	printf("%d\n", ans) ;
}

用f[i]表示S的前i个字符是否满足条件，初始状态是f[0]=1。状态转移时，可以枚举P的每一个元素，如果它是S的前i个字符组成的字符串的后缀，那么可以把当前状态转移到去掉这个后缀之后的状态。最终答案是能够使f[i]等于1的最大的i。

f[0] = 1;
for (int i = 1; i <= s.size(); i++)
    for (int j = 1; j <= n; j++)
        if (i >= p[j].size() && s.substr(i - p[j].size(), p[j].size()) == p[j])
            f[i] |= f[i - p[j].size()];

这是一道DP题

[USACO2.3] 最长前缀 Longest Prefix

这道题显然满足 1D/1D 动态规划的性质

我们开一个 $bool$ 类型的 $dp$ 数组，用 $dp_i$ 表示字符串前 $i$ 个字符是否可以分解为集合中的字符串

$dp_i$ 为 $true$ 的条件为：

• 存在一个比 $i$ 小的 $j$ ，满足 $dp_j$ 为真，而且从 $j+1$ 到 $i$ 是集合中的一个元素

这里可以用到 $substr$ 函数来表示 $str$ 从 $j+1$ 到 $i$ 的子串：

• $str.substr(i-len,len)$
• 其中 $len$ 为集合中某一元素的长度

以下是 100pts 代码：

#include<bits/stdc++.h>
using namespace std;
int ans,cnt=0;
string str,p[205],x;
bool dp[200005];
int main(){
	for(string s;cin>>s,s!=".";p[cnt++]=s);
	for(string s;cin>>s;str+=s);
	dp[0]=true;
	for(int i=1;i<=str.size();i++){
		dp[i]=0;
		for(int j=0;j<cnt;j++){
			int len=p[j].size();
			if(i>=len&&dp[i-len]&&p[j]==str.substr(i-len,len)){
				ans=i;
				dp[i]=1;
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
    QwQ;
}

难度：普及 / 提高-

luogu传送门

#include <bits/stdc++.h> using namespace std ; set<string> P[15] ; string s, z ; bool dp[200005] ; int len, m = 0, ans = 0 ; int main() { std::ios::sync_with_stdio(false) ; std::cin.tie(0) ; while(cin >> s) { if(s[0] == '.') break ; len = s.length() ; P[len].insert(s) ; m = max(m, len) ; } z = " " ; while(cin >> s) z = z + s ; len = z.length() ; dp[0] = 1 ; for(int i = 1; i < len; i ++)//此处为小于 { for(int j = min(i, m); j >= 1; j --) { s = z.substr(i - j + 1, j) ; if(P[s.length()].count(s) && dp[i - j]) { dp[i] = 1 ; ans = i ; } } } printf("%d\n", ans) ; }

#include <bits/stdc++.h>
using namespace std ;
set<string> P[15] ;
string s, z ; 
bool dp[200005] ;
int len, m = 0, ans = 0 ;
int main()
{
	std::ios::sync_with_stdio(false) ;
	std::cin.tie(0) ;
	while(cin >> s)
	{
		if(s[0] == '.') break ;
		len = s.length() ;
		P[len].insert(s) ;
		m = max(m, len) ;
	}
	z = " " ;
	while(cin >> s) z = z + s ;
	len = z.length() ;
	dp[0] = 1 ;
	for(int i = 1; i < len; i ++)//此处为小于 
	{
		for(int j = min(i, m); j >= 1; j --)
		{
			s = z.substr(i - j + 1, j) ;
			if(P[s.length()].count(s) && dp[i - j])
			{
				dp[i] = 1 ;
				ans = i ;
			}
		}
	}
	printf("%d\n", ans) ;
}