题解：洛谷 P1470 [USACO2.3] 最长前缀 Longest Prefix

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1470 [USACO2.3] 最长前缀 Longest Prefix - 洛谷【题目描述】在生物学中一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列即元素很感兴趣。如果一个集合P PP中的元素可以串起来元素可以重复使用组成一个序列s ss那么我们认为序列s ss可以分解为P PP中的元素。元素不一定要全部出现如下例中BBC就没有出现。举个例子序列ABABACABAAB可以分解为下面集合中的元素{A,AB,BA,CA,BBC}序列s ss的前面k kk个字符称作s ss中长度为k kk的前缀。设计一个程序输入一个元素集合以及一个大写字母序列设s ′ s′s′是序列s ss的最长前缀使其可以分解为给出的集合P PP中的元素求s ′ s′s′的长度k kk。【输入】输入数据的开头包括若干个元素组成的集合O OO用连续的以空格分开的字符串表示。字母全部是大写数据可能不止一行。元素集合结束的标志是一个只包含一个.的行集合中的元素没有重复。接着是大写字母序列s ss长度为用一行或者多行的字符串来表示每行不超过76 7676个字符。换行符并不是序列s ss的一部分。【输出】只有一行输出一个整数表示S SS符合条件的前缀的最大长度。【输入样例】A AB BA CA BBC . ABABACABAABC【输出样例】11【核心思想】问题分析给定一个单词集合P PP和一个目标字符串s ss要求找到s ss的最长前缀使其可以被P PP中的单词拼接而成单词可重复使用。这是一个字符串拼接 动态规划问题。算法选择方法一DP 直接匹配f [ i ] f[i]f[i]表示前i ii个字符能否被表示对每个位置枚举所有单词检查是否匹配方法二DP KMP 预处理先用 KMP 算法预处理每个单词在s ss中的所有匹配位置再用 DP 转移关键步骤读入数据读取单词集合以.结束再读取目标字符串可能多行方法一直接匹配初始化f [ 0 ] 1 f[0] 1f[0]1空串可表示遍历i ii从1 11到l e n lenlen遍历每个单词s [ j ] s[j]s[j]若i ≥ ∣ s [ j ] ∣ i \ge |s[j]|i≥∣s[j]∣且f [ i − ∣ s [ j ] ∣ ] 1 f[i - |s[j]|] 1f[i−∣s[j]∣]1且str.substr(i-|s[j]|, |s[j]|) s[j]f [ i ] 1 f[i] 1f[i]1更新a n s i ans iansi跳出内层循环方法二KMP 优化对每个单词p [ c ] p[c]p[c]执行 KMP预处理pl[c][i]表示该单词在s ss的位置i ii结束处是否匹配DP 转移d p [ i ] d p [ i ] ∨ d p [ i − l e n [ j ] ] dp[i] dp[i] \lor dp[i - len[j]]dp[i]dp[i]∨dp[i−len[j]]若单词j jj在位置i ii匹配从后往前找最大的i ii使d p [ i ] 1 dp[i] 1dp[i]1输出最长可表示前缀长度a n s ansans时间/空间复杂度方法一O ( l e n ⋅ ∣ P ∣ ⋅ L ) O(len \cdot |P| \cdot L)O(len⋅∣P∣⋅L)L LL为单词最大长度直接子串比较方法二O ( c ⋅ ( n L ) c ⋅ n ) O(c \cdot (n L) c \cdot n)O(c⋅(nL)c⋅n)KMP 预处理O ( c ⋅ n ) O(c \cdot n)O(c⋅n)DP 转移O ( c ⋅ n ) O(c \cdot n)O(c⋅n)空间复杂度O ( n ) O(n)O(n)或O ( c ⋅ n ) O(c \cdot n)O(c⋅n)动态规划的核心思想状态定义f [ i ] f[i]f[i]表示前i ii个字符能否被单词集合表示具有最优子结构转移方程f [ i ] ⋁ j ( f [ i − ∣ s j ∣ ] ∧ match ( s j , s t r [ i − ∣ s j ∣ . . i − 1 ] ) ) f[i] \bigvee_{j} (f[i - |s_j|] \land \text{match}(s_j, str[i-|s_j|..i-1]))f[i]⋁j​(f[i−∣sj​∣]∧match(sj​,str[i−∣sj​∣..i−1]))KMP 加速匹配避免每次O ( L ) O(L)O(L)的子串比较将单次匹配降至O ( n ) O(n)O(n)前缀特性只关心最长前缀因此 DP 按顺序处理遇到不可表示的位置后续仍可继续尝试适用于单词拆分、字符串拼接、模式匹配类问题【解题思路】【算法标签】#普及 #KMP【代码详解】#includebits/stdc.husingnamespacestd;string s[210];// 存储单词的数组string str;// 存储输入的目标字符串boolf[200010];// 动态规划数组f[i]表示前i个字符能否被单词组合intmain(){intk;// 读取单词列表直到遇到.结束for(k1;;k){string ss;cinss;if(ss.){break;}s[k]ss;}// 读取目标字符串可能有多行string ss;while(cinss){strss;}// 初始化动态规划数组f[0]1;// 空字符串可以被表示intans0;intlenstr.size();// 动态规划处理for(inti1;ilen;i){for(intj1;jk;j){intls[j].size();// 当前单词的长度// 检查前i-l个字符能否被表示且当前子串是否匹配单词if(ilf[i-l]s[j]str.substr(i-l,l)){f[i]1;// 标记前i个字符可以被表示ansi;// 更新最大可表示长度break;// 找到一个匹配即可}}}// 输出结果coutansendl;return0;}// 使用KMP算法再写一遍#includebits/stdc.husingnamespacestd;// 全局变量声明intc,n;// c: 模式串数量n: 目标串长度intlen[205];// 存储每个模式串的长度intk[205][15];// KMP算法的next数组boolpl[205][200005];// pl[i][j]表示模式串i在目标串j位置有匹配booldp[200005];// dp[i]表示目标串前i个字符能否被模式串组合string s,p[205];// s: 目标串p: 模式串数组/** * KMP算法预处理和匹配 * param c 当前处理的模式串索引 */voidkmp(intc){string p1p[c];// 当前模式串// 初始化next数组k[c][0]k[c][1]0;// 计算next数组for(inti2,j0;ilen[c];i){while(jp1[i]!p1[j1]){jk[c][j];}if(p1[i]p1[j1]){j;}k[c][i]j;}// 在目标串中进行模式匹配for(inti1,j0;in;i){while(js[i]!p1[j1]){jk[c][j];}if(s[i]p1[j1]){j;}if(jlen[c])// 找到完整匹配{pl[c][i]1;// 标记匹配位置}}}intmain(){// 读取模式串直到遇到.结束for(c1;;c){string ss;cinss;if(ss.){break;}p[c]ss;len[c]p[c].size();p[c]0p[c];// 添加前缀方便索引}c--;// 调整模式串数量// 读取目标串可能有多行string ss;while(cinss){sss;}ns.size();s0s;// 添加前缀方便索引// 对每个模式串执行KMP算法for(inti1;ic;i){kmp(i);}// 动态规划处理dp[0]1;// 空串可以被表示for(inti1;in;i){for(intj1;jc;j){if(pl[j][i])// 如果模式串j在位置i有匹配{dp[i]dp[i]||dp[i-len[j]];// 状态转移}}}// 从后往前查找最大可表示长度for(intin;i1;i--){if(dp[i]){coutiendl;return0;}}// 如果没有找到输出0cout0;return0;}【运行结果】A AB BA CA BBC . ABABACABAABC 11