题目名称 2108. [NOIP 2015] 子串
输入输出 2015substring.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2015-11-09
开放分组 全部用户
提交状态
分类标签
通过:165, 提交:665, 通过率:24.81%
GravatarRegnig Etalsnart 100 0.034 s C++
Gravatar123 100 0.079 s C++
Gravatarcy 100 0.088 s C++
Gravatardateri 100 0.090 s C++
Gravatarwmez 100 0.092 s C++
Gravatarcy 100 0.092 s C++
GravatarKZNS 100 0.108 s C++
GravatarFoolMike 100 0.112 s C++
GravatarMarvolo 100 0.116 s C++
GravatarPine 100 0.120 s C++
关于 子串 的讨论
一道动态规划嘛。。。算法是O(k*m*n)的,不算复杂,记得用滚动数组,否则内存会爆掉。。。
Gravatar琴殇''遙暩焱鐄
2015-11-12 21:28 1楼
Gravatarzys
2015-12-09 07:45 2楼
Gravatar0
2016-06-16 06:12 3楼
手欠,非要用gets,读入崩了
然后换成scanf AC!!
Gravatar2018YaLi稳
2016-05-03 21:08 4楼
看了N个人的题解,终于稀里糊涂地过了
GravatarAHOI_521
2016-06-15 21:36 5楼
表示O(nmk^2)也A了,表示不用滚动也a了。数据太弱。。【无耻地看了数据
Gravatarljt
2016-07-21 12:38 6楼
数据够弱的...第二次循环赋值的时候把0赋成1了都可以得60分=_=
Gravatarrvalue
2016-08-19 17:06 7楼
目前网上仍未有我的dp方程……
Gravatarconfoo
2016-09-03 09:27 8楼
今年我要爆零NOIP!(反flag)
Gravatar小一米
2016-09-10 10:50 9楼
Gravatarzihahahaha
2016-09-17 20:04 10楼
终于A了,不枉我写了一节课!!!
GravatarAntiLeaf
2016-09-26 11:41 11楼
GravatarLOSER
2016-10-23 21:45 12楼
数组开小是W不是E??
GravatarShirry
2017-09-07 17:02 13楼
为什么觉得我写的好奇怪
还有取模..又被坑
补补取模加模再取模
GravatarHyoi_Turkey
2017-09-14 08:59 14楼
………………
Gravatar+1s
2017-09-16 14:05 15楼
怂题解..........%大佬们
Gravatar҉҉ Hzoi_Goodboy
2017-11-08 21:35 16楼

2108. [NOIP 2015] 子串

★★☆   输入文件:2015substring.in   输出文件:2015substring.out   简单对比
时间限制:1 s   内存限制:128 MB

【题目描述】

有两个仅包含小写英文字母的字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串 B 相等?注意:子串取出的位置不同也认为是不同的方案。

【输入格式】

第一行是三个正整数 n,m,k,分别表示字符串 A 的长度,字符串 B 的长度,以及问题描述中所提到的 k,每两个整数之间用一个空格隔开。 第二行包含一个长度为 n 的字符串,表示字符串 A。 第三行包含一个长度为 m 的字符串,表示字符串 B。

【输出格式】

输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求输出答案对 1,000,000,007 取模的结果。

【样例输入1】

6 3 1 
aabaab 
aab

【样例输出1】

2

【样例输入2】

6 3 2 
aabaab 
aab

【样例输出2】

7

【样例输入3】

6 3 3 
aabaab 
aab

【样例输出1】

7

【提示】

对于第 1 组数据:1≤n≤500,1≤m≤50,k=1;

对于第 2 组至第 3 组数据:1≤n≤500,1≤m≤50,k=2;

对于第 4 组至第 5 组数据:1≤n≤500,1≤m≤50,k=m;

对于第 1 组至第 7 组数据:1≤n≤500,1≤m≤50,1≤k≤m;

对于第 1 组至第 9 组数据:1≤n≤1000,1≤m≤100,1≤k≤m;

对于所有 10 组数据:1≤n≤1000,1≤m≤200,1≤k≤m。

【来源】

在此键入。