本文分享的必刷题目是从蓝桥云课、洛谷、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

【核心思想】

1. 问题分析：给定一个单词集合P PP和一个目标字符串s ss，要求找到s ss的最长前缀，使其可以被P PP中的单词拼接而成（单词可重复使用）。这是一个字符串拼接 + 动态规划问题。

2. 算法选择：

   • 方法一：DP + 直接匹配：f [ i ] f[i]f[i]表示前i ii个字符能否被表示，对每个位置枚举所有单词检查是否匹配
   • 方法二：DP + KMP 预处理：先用 KMP 算法预处理每个单词在s ss中的所有匹配位置，再用 DP 转移

3. 关键步骤：

   • 读入数据：读取单词集合（以.结束），再读取目标字符串（可能多行）
   • 方法一（直接匹配）：
     • 初始化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 = ians=i，跳出内层循环
   • 方法二（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

4. 时间/空间复杂度：

   • 方法一：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⋅(n+L)+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)

5. 动态规划的核心思想：

   • 状态定义：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

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;string s[210];// 存储单词的数组string str;// 存储输入的目标字符串boolf[200010];// 动态规划数组，f[i]表示前i个字符能否被单词组合intmain(){intk;// 读取单词列表，直到遇到"."结束for(k=1;;k++){string ss;cin>>ss;if(ss=="."){break;}s[k]=ss;}// 读取目标字符串（可能有多行）string ss;while(cin>>ss){str+=ss;}// 初始化动态规划数组f[0]=1;// 空字符串可以被表示intans=0;intlen=str.size();// 动态规划处理for(inti=1;i<=len;i++){for(intj=1;j<k;j++){intl=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;return0;}

// 使用KMP算法再写一遍#include<bits/stdc++.h>usingnamespacestd;// 全局变量声明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 p1=p[c];// 当前模式串// 初始化next数组k[c][0]=k[c][1]=0;// 计算next数组for(inti=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(inti=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;// 标记匹配位置}}}intmain(){// 读取模式串，直到遇到"."结束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(inti=1;i<=c;i++){kmp(i);}// 动态规划处理dp[0]=1;// 空串可以被表示for(inti=1;i<=n;i++){for(intj=1;j<=c;j++){if(pl[j][i])// 如果模式串j在位置i有匹配{dp[i]=dp[i]||dp[i-len[j]];// 状态转移}}}// 从后往前查找最大可表示长度for(inti=n;i>=1;i--){if(dp[i]){cout<<i<<endl;return0;}}// 如果没有找到，输出0cout<<0;return0;}

【运行结果】

A AB BA CA BBC . ABABACABAABC 11