1. Of course reachable by suffix links. Total score in vertex = score[suff_link(vertex)] + (m_i if vertex is terminal else 0).
2. So it is the reason you use second argument — vertex in trie. vertex give you an information about your suffix.

Dynamic on Aho-Corasik trie.

For each vertex in trie we need to calculate the summary score which it will give(sum of all scores in terminate vertexes which can be reached from vertex).

Then dp[n][v] = max score we can receive if we have written n letters staying on vertex v. From each state we can go to 26 other states. O(n*m*k^2)

//init trie and calculate scores
for n = 0..k-1: //k
  for v = 0..|trie|: // O(n*k)
    for char in alphabet: // m
      u = go(v, char)
      dp[n+1][u] = max(dp[n+1][u], dp[n][v]+score[u])
//answer = max(dp[k][v] for each v)

Interesting problem.

Idea: Make 2^N similar Aho-Corasick trie graphs. mask-th graph means that you have already written words from this mask(i-th digit in 2-based numeral system equals 1 if you have written i-th word). You should find a path of least length that connect 0-graph and (2^N-1) graph. You have only 0-weighted(connect graphs) and 1-weighted(connect vertexes) edges. So you can use 0-1 bfs with O(|E|)=O(2^N * |trie| * 26) that should pass tests:)

In Aho-Corasick trie you should prohibit all jumps that lead to forbidden words.

Also you can solve this problem.

P.s. It is a good practice to share a link to your problem.

import sys 
for line in sys.stdin: 
  #type your code here

• line is a string from stdin.
• line contains '\n'.
• Don't forget to use strip().