Gift and Chef
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Last week Penguin Charlie had a birthday. Chef presented him a string S.
Unfortunately, Charlie doesn't like string S, he likes string F. Charlie wants to create a few strings F from S by cutting. Cutting means getting some substrings from S that are equal to F and delete them from string S. After deleting a substring, the left and right parts of the resulting string remain separated. Note, a substring of a string S is a consecutive sequence of characters in S.
In some cases Charlie can still get substrings equal to F from the pieces that remain after cutting the original string. Your task is to calculate the number of ways to cut out at least one occurrence of the substring F in S. As this number may be too large, print it modulo 109 + 7.
Input begins with an integer T: the number of test cases.
Each test case consists of a two lines with two strings: S, F.
For each test case, output a single line indicating the number of ways Charlie can cut at least one occurrence of F from S modulo 109 + 7.
Constraints and Subtasks
- 1 ≤ T ≤ 10
- 1 ≤ |F| ≤ |S| ≤ 100
- 1 ≤ |F| ≤ |S| ≤ 5000
- 1 ≤ |F| ≤ |S| ≤ 300000
Subtask 1 : 10 points
Subtask 2 : 30 points
Subtask 3 : 60 points
Input: 3 chefandcharliethebest charliethebest heknowsimeanityeahyouknowimeanityouknow imeanit aaaaa aa Output: 1 3 7
Example case 1.
1 way to cut 1 string "charliethebest" from the string S:
Example case 2.
2 ways to cut 1 string "imeanit" from the string S - take one of them
1 way to cut 2 strings "imeanit" from the string S - take both:
Example case 3.
4 ways to cut 1 string "aa" from the string "aaaaa": |aa|aaa, a|aa|aa, aa|aa|a, aaa|aa|
3 ways to cut 2 strings "aa" from the string "aaaaa": |aa||aa|a, |aa|a|aa|, a|aa||aa|.
|Tags||dynamic-programming, easy, kmp, nov16, omelyanenko|
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions