Order preserving matching refers to the problem of reporting substrings in the text which are order-isomorphic to the pattern. In this paper, we show a simple heuristic which runs in linear time on average, based on finding the largest elements in each substring and checking their locations against that of the pattern. It is easy to implement and experimental results showed that the running time grows linearly.

Succinct representation is a space-efficient method to represent n discrete objects using space close to the information-theoretic lower bound. In order to directly access the ith object of succinctly represented data structures in constant time, two fundamental functions, rank and select, are commonly used. In this paper we propose two implementations supporting rank and select in constant time for non-compressed bit strings. One uses O(n log log n / ) bits of extra space and the other uses n+O(n log log n / log n) bits of extra space in the worst case. The former is rather a theoretical algorithm and the latter is a practical algorithm which works faster and uses less space in practice.