deciding if a pattern formula_32 of length formula_33 is a substring of a string formula_7 of length formula_11 takes formula_36 time if only the suffix array is used. by additionally using the lcp information, this bound can be improved to formula_37 time. show how to improve this running time even further to achieve optimal formula_38 time. thus, using suffix array and lcp array information, the decision query can be answered as fast as using the suffix tree.