Counting shared starts in a set of traversal orderings

A graph has n vertices. A tool has run depth-first search on it many times, with each run visiting the neighbours of a vertex in a different order. We have recorded N of the orderings it produced. Each ordering is the sequence of all n vertices in the order that the run visited them. Every run started at the same vertex.

These 8 orderings of one graph on 8 vertices are an example:

1  ahbfdceg
2  aedfbhgc
3  aghbcdfe
4  aedcbhgf
5  ahbfdecg
6  ahgbedcf
7  aedfhbcg
8  ahfdebcg

You have to design a data structure that can answer how many of the recorded orderings begin with a given sequence of m vertices. For example, how many of the 8 orderings above start with the sequence ahb? (The answer would be 2.)

Give the following in your answer:

1. Describe the data structure, including what is stored at each of its nodes.
2. Explain how the data structure can be used to answer the query, and why it gives the correct answer.
3. State and justify the time required to build the data structure and the time to answer the query (in terms of N, n and m).

Write in plain text. You may write a running time as Theta(...) or O(...).