302556: CF494B. Obsessive String
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Obsessive String
题意翻译
【题目描述】 Hamed最近发现了一个字符串T,然后突然就很喜爱这个字符串。他花了一些时间试图找出所有包含T为子串的其他字符串。最后,他变得很累,然后开始考虑下面的问题。 给你一个字符串S,问你有多少种方式提取长度不为0的不重叠的子串,每个子串都必须包含字符串T。 更正式地说,你需要计算选择两个序列A和B,满足以下要求 k>=1 ![](https://cdn.luogu.org/upload/vjudge_pic/CF494B/bb2a9663e220d590c509be53cd8da3ca9ca602e8.png) ![](https://cdn.luogu.org/upload/vjudge_pic/CF494B/15cb6228063cc47cd8627d4598e4f8fe6e9779d4.png) ![](https://cdn.luogu.org/upload/vjudge_pic/CF494B/bb2a9663e220d590c509be53cd8da3ca9ca602e8.png) ![](https://cdn.luogu.org/upload/vjudge_pic/CF494B/24d9cacc311eaf7cd7460855212493822ca3c22b.png) 因为输出数字太大,所以要mod 10^9+7 。 【输入】 输入总共两行 第一行输入一个字符串S 第二行输入一个字符串T 【输出】 输出一个数字,代表可行的方案数。题目描述
Hamed has recently found a string $ t $ and suddenly became quite fond of it. He spent several days trying to find all occurrences of $ t $ in other strings he had. Finally he became tired and started thinking about the following problem. Given a string $ s $ how many ways are there to extract $ k>=1 $ non-overlapping substrings from it such that each of them contains string $ t $ as a substring? More formally, you need to calculate the number of ways to choose two sequences $ a_{1},a_{2},...,a_{k} $ and $ b_{1},b_{2},...,b_{k} $ satisfying the following requirements: - $ k>=1 $ - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF494B/c5deac271ac89767b4839ccdea2b77dd1eb1d964.png) - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF494B/15cb6228063cc47cd8627d4598e4f8fe6e9779d4.png) - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF494B/bb2a9663e220d590c509be53cd8da3ca9ca602e8.png) - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF494B/24d9cacc311eaf7cd7460855212493822ca3c22b.png) $ t $ is a substring of string $ s_{ai}s_{ai}+1... s_{bi} $ (string $ s $ is considered as $ 1 $ -indexed). As the number of ways can be rather large print it modulo $ 10^{9}+7 $ .输入输出格式
输入格式
Input consists of two lines containing strings $ s $ and $ t $ ( $ 1<=|s|,|t|<=10^{5} $ ). Each string consists of lowercase Latin letters.
输出格式
Print the answer in a single line.
输入输出样例
输入样例 #1
ababa
aba
输出样例 #1
5
输入样例 #2
welcometoroundtwohundredandeightytwo
d
输出样例 #2
274201
输入样例 #3
ddd
d
输出样例 #3
12