SuffixTree { public boolean containsSuffix(Sequence seq) { int state = root; int i = 0; while (true) { final int edge = findEdge(state, seq.objectAt(i)); if (edge < 0) { return false; } int j = getStartIndex(edge); final int m = getEndIndex(edge) + 1; for (; i < seq.size() && j < m; j++, i++) { if (seq.objectAt(i) != this.sequence.objectAt(j)) { return false; } } if (i == seq.size()) { return j == inputSize; } state = getToState(edge); } } SuffixTree(
      Sequence sequence,
      IStateCallback newStateCallback,
      final IProgressCallback progressCallback); final int getTransitionsCount(); final int getStatesCount(); boolean containsSuffix(Sequence seq); final void visit(final IVisitor visitor); final void visitState(final int state, final IVisitor visitor); int getRootState(); final boolean isLeaf(int state); final int firstEdge(int state); final int nextEdge(int edge); final int findEdge(int state, int symbol); int getToState(int edge); int getStartIndex(int edge); int getEndIndex(int edge); static final int NO_EDGE; }
@Test public void checkRandomSymbols() { final int[] input = new int[scaledRandomIntBetween(1, 25000)]; for (int i = 0; i < input.length; i++) { input[i] = randomIntBetween(0, 100); } input[input.length - 1] = Integer.MAX_VALUE; final SuffixTree stree = SuffixTreeBuilder.from( new Sequence() { public int objectAt(int i) { return input[i]; } public int size() { return input.length; } }) .build(); for (int i = 0; i < Math.min(5000, input.length); i++) { stree.containsSuffix(new IntegerSequence(input, i, input.length - i)); } }
@Test public void testContainsSuffix() { final SuffixTree stree = SuffixTreeBuilder.from(new CharacterSequence("cocoa$")).build(); assertFalse(stree.containsSuffix(new CharacterSequence("c"))); assertFalse(stree.containsSuffix(new CharacterSequence("co"))); assertFalse(stree.containsSuffix(new CharacterSequence("coc"))); assertFalse(stree.containsSuffix(new CharacterSequence("coco"))); assertFalse(stree.containsSuffix(new CharacterSequence("cocoa"))); assertFalse(stree.containsSuffix(new CharacterSequence("cx"))); assertFalse(stree.containsSuffix(new CharacterSequence("cox"))); assertFalse(stree.containsSuffix(new CharacterSequence("cocx"))); assertFalse(stree.containsSuffix(new CharacterSequence("cocox"))); assertFalse(stree.containsSuffix(new CharacterSequence("cocoax"))); assertFalse(stree.containsSuffix(new CharacterSequence("cocoa$x"))); assertFalse(stree.containsSuffix(new CharacterSequence("x"))); }