【题目来源】
洛谷：[P1470 USACO2.3] 最长前缀 Longest Prefix - 洛谷
【题目描述】
在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列（即元素）很感兴趣。
如果一个集合 \(P\) 中的元素可以串起来（元素可以重复使用）组成一个序列 \(s\) ，那么我们认为序列 \(s\) 可以分解为 \(P\) 中的元素。元素不一定要全部出现（如下例中 BBC 就没有出现）。举个例子，序列 ABABACABAAB 可以分解为下面集合中的元素：{A,AB,BA,CA,BBC}
序列 \(s\) 的前面 \(k\) 个字符称作 \(s\) 中长度为 \(k\) 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列 ，设 \(s′\) 是序列 \(s\) 的最长前缀，使其可以分解为给出的集合 \(P\) 中的元素，求 \(s′\) 的长度 \(k\)。
【输入】
输入数据的开头包括若干个元素组成的集合 \(O\)，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 . 的行，集合中的元素没有重复。
接着是大写字母序列 \(s\) ，长度为，用一行或者多行的字符串来表示，每行不超过 \(76\) 个字符。换行符并不是序列 \(s\) 的一部分。
【输出】
只有一行，输出一个整数，表示 \(S\) 符合条件的前缀的最大长度。
【输入样例】
A AB BA CA BBC
.
ABABACABAABC
【输出样例】
11
【解题思路】
【算法标签】
《洛谷 P1470 最长前缀》 #字符串# #动态规划,dp# #KMP# #USACO#
【代码详解】
#include <bits/stdc++.h>
using namespace std;string s[210]; // 存储单词的数组
string str; // 存储输入的目标字符串
bool f[200010]; // 动态规划数组，f[i]表示前i个字符能否被单词组合int main()
{int k;// 读取单词列表，直到遇到"."结束for (k = 1; ; k++){string ss;cin >> ss;if (ss == "."){break;}s[k] = ss;}// 读取目标字符串（可能有多行）string ss;while (cin >> ss){str += ss;}// 初始化动态规划数组f[0] = 1; // 空字符串可以被表示int ans = 0;int len = str.size();// 动态规划处理for (int i = 1; i <= len; i++){for (int j = 1; j < k; j++){int l = s[j].size(); // 当前单词的长度// 检查前i-l个字符能否被表示，且当前子串是否匹配单词if (i >= l && f[i - l] && s[j] == str.substr(i - l, l)){f[i] = 1; // 标记前i个字符可以被表示ans = i; // 更新最大可表示长度break; // 找到一个匹配即可}}}// 输出结果cout << ans << endl;return 0;
}
// 使用KMP算法再写一遍
#include <bits/stdc++.h>
using namespace std;// 全局变量声明
int c, n; // c: 模式串数量，n: 目标串长度
int len[205]; // 存储每个模式串的长度
int k[205][15]; // KMP算法的next数组
bool pl[205][200005]; // pl[i][j]表示模式串i在目标串j位置有匹配
bool dp[200005]; // dp[i]表示目标串前i个字符能否被模式串组合
string s, p[205]; // s: 目标串，p: 模式串数组/*** KMP算法预处理和匹配* @param c 当前处理的模式串索引*/
void kmp(int c)
{string p1 = p[c]; // 当前模式串// 初始化next数组k[c][0] = k[c][1] = 0;// 计算next数组for (int i = 2, j = 0; i <= len[c]; i++){while (j && p1[i] != p1[j + 1]){j = k[c][j];}if (p1[i] == p1[j + 1]){j++;}k[c][i] = j;}// 在目标串中进行模式匹配for (int i = 1, j = 0; i <= n; i++){while (j && s[i] != p1[j + 1]){j = k[c][j];}if (s[i] == p1[j + 1]){j++;}if (j == len[c]) // 找到完整匹配{pl[c][i] = 1; // 标记匹配位置}}
}int main()
{// 读取模式串，直到遇到"."结束for (c = 1; ; c++){string ss;cin >> ss;if (ss == "."){break;}p[c] = ss;len[c] = p[c].size();p[c] = '0' + p[c]; // 添加前缀方便索引}c--; // 调整模式串数量// 读取目标串（可能有多行）string ss;while (cin >> ss){s += ss;}n = s.size();s = '0' + s; // 添加前缀方便索引// 对每个模式串执行KMP算法for (int i = 1; i <= c; i++){kmp(i);}// 动态规划处理dp[0] = 1; // 空串可以被表示for (int i = 1; i <= n; i++){for (int j = 1; j <= c; j++){if (pl[j][i]) // 如果模式串j在位置i有匹配{dp[i] = dp[i] || dp[i - len[j]]; // 状态转移}}}// 从后往前查找最大可表示长度for (int i = n; i >= 1; i--){if (dp[i]){cout << i << endl;return 0;}}// 如果没有找到，输出0cout << 0;return 0;
}
【运行结果】
A AB BA CA BBC
.
ABABACABAABC
11