Problem Description:
If one is given a string of length N,
there are two ways of specifying substrings of it. One way is to give the
string representation, namely the substring itself. The other way is to specify
a numeric subsequence of the numbers (1,2,3,... N). These correspond to the
positions in the original string of the characters of the substring.
Thus if the string "tcsin",
the numeric subsequence (1,3,5) represents the substring whose characters are
from the positions 1,3,5 from the original string, or the substring "tsn".
Regular expressions are a very
standard way to represent patterns in strings. One symbol in it is
"+", which represents all strings that have one or more occurrences
of the preceding character. Thus the regular expression t+c+s+i+n+ represents any
string which has a string of t's followed by a string of c's followed by a
string of s's followed by a string of i's followed by a string of n's. Each of
these strings of repeating letters must have at leat one character. Thus
ttcsssiiiiinn, tcsin, tcccsiin all satisfy it, while tcin does not (the string
of s's has 0 characters) and tscin does not (the string of c's is after the
string of c's, when it should be before).
If the length of the string is N, the
objective is to count the number of distinct numeric subsequences of (1,2,3,...
N) that correspond to a substring that matches the regular expression
t+c+s+i+n+
Input
The input will be one line of a string
of letters.
Output
The output is the remainder when the
number of distinct numeric subsequences is divided by (109+7)
Constraints
5≤ N ≤ 105
Example 1
Input:
tcstcsin
Output:
7
Explanation:
Here, N is 8, and we are looking for
distinct subsequences of (1,2,...8). The distinct numeric subsequences and the
corresponding substrings are given. It may be seen that all the substrings
match the regular expression, and there are no more numeric subsequences that
correspond to substrings that match the regular expression. As there are 7
distinct numeric subsequences, the output is 7. [the remainder when 7 is
divided by (109+7)]
Numeric Substring
(1,2,3,7,8) tcsin
(1,2,3,6,7,8) tcssin
(1,2,6,7,8) tcsin
(1,2,5,6,7,8) tccsin
(1,5,6,7,8) tcsin
(1,4,5,6,7) ttcsin
(4,5,6,7) tcsin
Example 2
Input:
tcsintcsin
Output:
11
Explanation:
Here, N is 10, and we are looking for
distinct subsequences of (1,2,...10). The distinct numeric subsequences and the
corresponding substrings are given. It may be seen that all the substrings
match the regular expression, and there are no more numeric subsequences that
correspond to substrings that match the regular expression. As there are 11
distinct numeric subsequences, the output is 11 [the remainder when 11 is
divided by (109+7)]
Numeric Substring
(1,2,3,4,10) tcsin
(1,2,3,4,5,10) tcsinn
(1,2,3,4,9,10) tcsiin
(1,2,3,4,10) tcsin
(1,2,3,8,9,10) tcssin
(1,2,8,9,10) tcsin
(1,2,8,9,10) tcsin
(1,2,7,8,9,10) tccsin
(1,7,8,9,10) tcsin
(1,6,7,8,9,10) ttcsin
(6,7,8,9,10) tcsin
(1,2,3,4,5) tcsin
No comments:
Post a Comment