Substreeng
SRM 696 · 2016-07-09 · by subscriber
SRM 696 · 2016-07-09 · by subscriber · Dynamic Programming
Problem Statement
Problem Statement
Hero has a tree.
As usual, the tree has n vertices labeled 0 through n-1.
Each edge of the tree has a one-character label.
You are given the description of the tree: a int[] par and a String ch with n-1 elements each.
For each valid i, the tree contains an edge between vertices (i+1) and par[i], and the label on the edge is ch[i].
For any ordered pair of vertices (x,y), the (x,y)-label is obtained as follows:
Consider the unique simple path from x to y.
For each edge on this path write down its label.
The (x,y)-label is the concatenation of those edge labels, in order.
We say that the tree contains a string S if there is a pair of vertices (x,y) such that S is the (x,y)-label.
You are given a String pat.
This string has a particular property: there are no adjacent equal characters in pat.
Hero wants to choose a subtree of his tree.
(A subtree is any nonempty connected subgraph.
Two subtrees are distinct if their sets of vertices differ.)
The chosen subtree should not contain the string pat.
Count the number of ways in which Hero can choose his subtree, and return that count modulo 10^9 + 7.
Constraints
- par will contain between 1 and 100 elements, inclusive.
- For each valid i, par[i] will be between 0 and i, inclusive.
- par and ch will contain the same number of elements.
- Each character in ch will be between 'a' and 'z', inclusive.
- pat will contain between 1 and 8 characters, inclusive.
- Each character in pat will be between 'a' and 'z', inclusive.
- There will be no equals adjacent characters in pat.
Examples
0)
{0,0,0}
"aab"
"ab"
Returns: 8
This tree contains the edges 1-0 (label 'a'), 2-0 (label 'a'), and 3-0 (label 'b'). Hero can choose a subtree that corresponds to one of the following 8 subsets of vertices: {0}, {1}, {2}, {3}, {0,1}, {0,2}, {0,1,2}, or {0,3}.
1)
{0,0,0}
"aaa"
"b"
Returns: 11
This tree has 11 different subtrees (including the tree itself), and Hero can choose any of them.
2)
{0,1,2,3}
"abab"
"ab"
Returns: 9
3)
{0,1,2,3,4,5,6,7,8}
"ababababa"
"c"
Returns: 55
4)
{0,1,2,3,4,5,6,7,8}
"ababababa"
"abab"
Returns: 34
Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Substreeng with a public method int count(vector<int> par, string ch, string pat) · 62 test cases · 2 s / 256 MB per case