def GetNumSuffixes(start_state):
  """Compute number of minimal suffixes automaton accepts from each state.

  For each state reachable from given state, compute number of paths in the
  automaton that start from that state, end in the accepting state and do not
  pass through accepting states in between.

  It is assumed that there are no cyclic paths going entirely through
  non-accepting states.

  Args:
    start_state: start state (as defined in dfa_parser.py).

  Returns:
    Dictionary from reachable states to numbers of suffixes.
  """
  num_suffixes = {}

  def ComputeNumSuffixes(state):
    if state in num_suffixes:
      return

    if state.is_accepting:
      num_suffixes[state] = 1

      # Even though the state itself is accepting, there may be more reachable
      # states behind it.
      for t in state.forward_transitions.values():
        ComputeNumSuffixes(t.to_state)

      return

    if state.any_byte:
      next_state = state.forward_transitions[0].to_state
      ComputeNumSuffixes(next_state)
      num_suffixes[state] = num_suffixes[next_state]
      return

    count = 0
    for t in state.forward_transitions.values():
      ComputeNumSuffixes(t.to_state)
      count += num_suffixes[t.to_state]
    num_suffixes[state] = count

  ComputeNumSuffixes(start_state)
  return num_suffixes