public MatchResult match(MatchResult reuse, byte[] sequence, int start, int length, int node) {
    if (node == 0) {
      reuse.reset(MatchResult.NO_MATCH, start, node);
      return reuse;
    }

    final FST fst = _fst;
    final int end = start + length;
    for (int i = start; i < end; i++) {
      final int arc = fst.getArc(node, sequence[i]);
      if (arc != 0) {
        if (i + 1 == end && fst.isArcFinal(arc)) {
          /* The automaton has an exact match of the input sequence. */
          reuse.reset(MatchResult.EXACT_MATCH, i, node);
          return reuse;
        }

        if (fst.isArcTerminal(arc)) {
          /* The automaton contains a prefix of the input sequence. */
          reuse.reset(MatchResult.AUTOMATON_HAS_PREFIX, i + 1, node);
          return reuse;
        }

        // Make a transition along the arc.
        node = fst.getEndNode(arc);
      } else {
        if (i > start) {
          reuse.reset(MatchResult.AUTOMATON_HAS_PREFIX, i, node);
        } else {
          reuse.reset(MatchResult.NO_MATCH, i, node);
        }
        return reuse;
      }
    }

    /* The sequence is a prefix of at least one sequence in the automaton. */
    reuse.reset(MatchResult.SEQUENCE_IS_A_PREFIX, 0, node);
    return reuse;
  }
@Test
  public void testAutomatonHasPrefixBug()
      throws Exception {
    FST fst = FSTBuilder.build(
        Arrays.asList("a".getBytes(UTF_8), "ab".getBytes(UTF_8), "abc".getBytes(UTF_8), "ad".getBytes(UTF_8),
            "bcd".getBytes(UTF_8), "bce".getBytes(UTF_8)), new int[]{10, 11, 12, 13, 14, 15});
    byte[] fstData = new FSTSerializerImpl().withNumbers().serialize(fst, new ByteArrayOutputStream()).toByteArray();
    fst = FST.read(new ByteArrayInputStream(fstData), ImmutableFST.class, true);

    FSTTraversal fstTraversal = new FSTTraversal(fst);
    assertEquals(fstTraversal.match("a".getBytes(UTF_8))._kind, EXACT_MATCH);
    assertEquals(fstTraversal.match("ab".getBytes(UTF_8))._kind, EXACT_MATCH);
    assertEquals(fstTraversal.match("abc".getBytes(UTF_8))._kind, EXACT_MATCH);
    assertEquals(fstTraversal.match("ad".getBytes(UTF_8))._kind, EXACT_MATCH);

    assertEquals(fstTraversal.match("b".getBytes(UTF_8))._kind, SEQUENCE_IS_A_PREFIX);
    assertEquals(fstTraversal.match("bc".getBytes(UTF_8))._kind, SEQUENCE_IS_A_PREFIX);

    MatchResult m = fstTraversal.match("abcd".getBytes(UTF_8));
    assertEquals(m._kind, AUTOMATON_HAS_PREFIX);
    assertEquals(m._index, 3);

    m = fstTraversal.match("ade".getBytes(UTF_8));
    assertEquals(m._kind, AUTOMATON_HAS_PREFIX);
    assertEquals(m._index, 2);

    m = fstTraversal.match("ax".getBytes(UTF_8));
    assertEquals(m._kind, AUTOMATON_HAS_PREFIX);
    assertEquals(m._index, 1);

    assertEquals(fstTraversal.match("d".getBytes(UTF_8))._kind, NO_MATCH);
  }