A new problem in string searching
George Havas and Jin Xian Lian

Abstract. We describe a substring search problem that arises in group 
presentation simplification processes. We suggest a two-level searching model:
skip and match levels. We give two timestamp algorithms which skip searching
parts of the text where there are no matches at all and prove their 
correctness. At the match level, we consider Harrison signature, Karp-Rabin
fingerprint, Bloom filter and automata based matching algorithms and present
experimental test figures.