String Matching with Variable Length Gaps

Philip Bille, Inge Li Goertz, Hjalte Wedel Vildhøj +1

We consider string matching with variable length gaps. Given a string $T$ and a pattern $P$ consisting of strings separated by variable length gaps (arbitrary strings of length in…