当前位置：首页 > web >正文

《P1470 [USACO2.3] 最长前缀 Longest Prefix》

web 2025/8/6 3:17:52

题目描述

在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列（即元素）很感兴趣。

如果一个集合 P 中的元素可以串起来（元素可以重复使用）组成一个序列 s ，那么我们认为序列 s 可以分解为 P 中的元素。元素不一定要全部出现（如下例中 BBC 就没有出现）。举个例子，序列 ABABACABAAB 可以分解为下面集合中的元素：{A,AB,BA,CA,BBC}

序列 s 的前面 k 个字符称作 s 中长度为 k 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，设 s′ 是序列 s 的最长前缀，使其可以分解为给出的集合 P 中的元素，求 s′ 的长度 k。

输入格式

输入数据的开头包括若干个元素组成的集合 P，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 . 的行，集合中的元素没有重复。

接着是大写字母序列 s ，用一行或者多行的字符串来表示，每行不超过 76 个字符。换行符并不是序列 s 的一部分。

输出格式

只有一行，输出一个整数，表示 S 符合条件的前缀的最大长度。

输入输出样例

输入 #1复制

A AB BA CA BBC
.
ABABACABAABC

输出 #1复制

说明/提示

【数据范围】

对于 100% 的数据，1≤card(P)≤200，1≤∣S∣≤2×105，P 中的元素长度均不超过 10。

翻译来自NOCOW

USACO 2.3

代码实现：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Trie树节点定义
struct TrieNode {
bool isEnd;
TrieNode* children[26];

TrieNode() {
isEnd = false;
for (int i = 0; i < 26; i++) {
children[i] = NULL;
}
}
};

// 插入单词到Trie树
void insert(TrieNode* root, const string& word) {
TrieNode* node = root;
for (int i = 0; i < word.length(); i++) {
int index = word[i] - 'A';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEnd = true;
}

int main() {
// 读取单词集合并构建Trie树
TrieNode* root = new TrieNode();
string line;

// 读取单词集合直到遇到单独的"."行
while (getline(cin, line) && line != ".") {
// 处理一行中可能有多个单词的情况
string word;
for (int i = 0; i < line.length(); i++) {
if (line[i] == ' ') {
if (!word.empty()) {
insert(root, word);
word.clear();
}
} else {
word += line[i];
}
}
// 处理行末的最后一个单词
if (!word.empty()) {
insert(root, word);
}
}

// 读取目标字符串S（多行输入，以空行结束）
string S;
while (getline(cin, line) && !line.empty()) {
S += line;
}
int n = S.length();

// dp[i]表示S的前i个字符是否可以被分解为单词集合中的单词
vector<bool> dp(n + 1, false);
dp[0] = true; // 空字符串可以被分解

// 记录最大前缀长度
int max_length = 0;

// 遍历每个位置
for (int i = 0; i < n; i++) {
if (!dp[i]) continue; // 如果之前的位置无法分解，跳过

// 从位置i开始尝试匹配所有可能的单词
TrieNode* current = root;
for (int j = i; j < n; j++) {
int index = S[j] - 'A';
if (!current->children[index]) break; // 路径不存在

current = current->children[index];
if (current->isEnd) { // 找到一个单词
dp[j + 1] = true;
if (j + 1 > max_length) {
max_length = j + 1;
}
}
}
}

cout << max_length << endl;

// 注意：这里省略了释放Trie树内存的代码

return 0;
}