On the Decision Tree Complexity of String Matching

Xiaoyu He, Neng Huang, Xiaoming Sun

String matching is one of the most fundamental problems in computer science. A natural problem is to determine the number of characters that need to be queried (i.e. the decision t…