首页 > 试题广场 >

寻找子串

[编程题]寻找子串

给出 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 展开全文

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

上传者：小小

难度：

17条回答 70收藏 9591浏览

查看代码

扫一扫，把题目装进口袋