Burdockvirus DNA
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
DNA (both of the burdockvirus, a human, and any other creature) can be represented as a string consisting of lowercase Latin letters.
As a result of long-term experiments, Zenik and Marichka built a theory of the effect of the burdockvirus on humans.
The similarity coefficient of two DNA sequences of the same length is defined as the sum of the indices (1-indexed) at which these sequences match.
The impact coefficient of a virus with DNA \(s\) on a human with DNA \(t\) is the sum of the similarity coefficients between \(s\) and all substrings of \(t\) of the same length as \(s\).
Write a program to find the impact coefficient of the virus on the human.
Input
The first line contains \(t\).
The second line contains \(s\).
Output
Print a single integer in one line — the impact coefficient of the virus with DNA \(s\) on the human with DNA \(t\).
Constraints
\(1 \le |t|, |s| \le 10^5\), where \(|x|\) is the length of the string \(x\),
\(s\) and \(t\) consist of lowercase Latin letters.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| abacaba ab | 7 |
Notes
Substrings of \(t\) of length 2:
ab, ba, ac, ca,
ab, ba.
Their similarity coefficients with \(s\): 3, 0, 1, 0, 3, 0.
\(3+0+1+0+3+0=7\).
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
Burdockvirus DNA - Editorial
What is the length of the shortest path that starts at the root of the tree, passes through all its leaves and returns to the root? It is easy to see that such a path goes along every edge exactly twice, so its length is \(2n - 2\), where \(n\) is the number of vertices of the tree.
How does this length change if we do not need to return to the root after visiting the last leaf? Let \(D_v\) be the distance from the root to vertex \(v\) (we also call it the depth of \(v\)). Clearly, ending at a leaf \(x\) saves exactly \(D_x\) edges. So it pays to end our route at the vertex with the largest \(D_v\).
So to answer a query of the second type, we need the number of vertices in the subtree and the depth of the deepest leaf. If there were no queries of the first type, it would be enough to compute these values for all vertices with a depth-first search. What about the queries of the first type? We move from adding vertices to "switching on" vertices. Consider the tree we get after all queries of the first type (we call it the final tree). Now each vertex of this tree is either switched on or not. A query of the first type switches on the corresponding vertex. For a query of the second type, we need the number of switched-on vertices in the subtree and the maximum depth among the switched-on vertices in the subtree.
Build the Euler tour of the final tree: write out all its vertices in the order of a depth-first search. Every subtree corresponds to a contiguous segment of this tour. This turns subtree queries into segment queries. So now we need a data structure that efficiently supports the following operations:
change the value of an element (to switch on a vertex)
find the sum on a segment (to find the number of vertices in a subtree)
find the maximum element on a segment (to find the deepest leaf)
One such structure is a segment tree. It handles each of these queries in logarithmic time.
Total complexity: \(O(n + q \log(n))\).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|