首页 > 试题广场 >

寻找子串

[编程题]寻找子串

给出 m 个字符串 S1，S2，...，Sm 和一个单独的字符串 T 。请在 T 中选出尽可能多的子串同时满足：

1）这些子串在 T 中互不相交。

2）这些子串都是 S1，S2，...，Sm 中的某个串。

问最多能选出多少个子串。

数据范围： $1 \le m \le 10 \$ ，输入的每个字符串长度满足 $1 \le n \le 10^5 \$

第一行一个数m（1≤m≤10），接下来m行，每行一个串。最后一行输入一个串T。输入中所有单个串的长度不超过100000，串中只会出现小写字母。

输出一个数，最多能选出多少串。

示例1

输入

3
aa
b
ac
bbaac

可选 b b aa 或 b b ac

算法知识视频讲解

烤冷面加辣白菜

发表于 2020-03-23 19:22:19

#include <iostream> #include <string.h> using namespace std; int m; const int maxn=100005; char T[maxn],S[15][maxn]; struct node { i 展开全文

重生之我要当分子

发表于 2025-01-01 14:28:13

解题思路这是一个字符串匹配和动态规划问题。使用算法找到所有模式串的匹配位置，然后用动态规划求解最大不相交子串数量。关键点：使用算法高效查找所有匹配位置用动态规划数组表示到位置的最大不相交子串数量对每个位置，考虑是否选择以该位置结尾的匹配算法步骤：对每个模式串进行展开全文

贪心 C++工程师动态规划安卓工程师字符串京东哈希 2019

上传者：小小

难度：

17条回答 71收藏 10815浏览

查看代码

寻找子串

扫一扫，把题目装进口袋