The construction of such a tree for the string formula_1 takes time and space linear in the length of formula_1. Once constructed, several operations can be performed quickly, for instance locating a substring in formula_1, locating a substring if a certain number of mistakes are allowed, locating matches for a regular expression pattern etc. Suffix trees also provide one of the first linear-time solutions for the longest common substring problem. These speedups come at a cost: storing a string's suffix tree typically requires significantly more space than storing the string itself.