Table of Contents 1Suffix arrays 2Searching methods2.1Naive \(O(|P|\cdot \lg_2 n)\) search 2.2Faster \(O(|P|\cdot \lg_2 n)\) search 2.3LCP-based \(O(|P| + \lg_2 n)\) search 3Analysing the faster search We’ll prove that using the “faster” binary search algorithm (see 2.2) that tracks the LCP with the left and right boundary of the remaining search interval has amortized runtime \[ O\Big(\lg_2(n) + |P| + |P| \cdot \lg_2(Occ(P))\Big), \] when \(P\) is a randomly sampled fixed-length patter...
