(aside image)

String Algorithms

The group develops and analyzes efficient algorithms for information retrieval. Our perspective is algorithm engineering. We consider both exact and approximate string searching as well as indexing methods. Also algorithms for data compression and computational biology are studied.

Slides: nutshell (pptx, pdf), highlights (pdf)


Present staff



Publications (recent)

S. Ghuman, J. Tarhio: Jumbled matching with SIMD. In: PSC '16, 15th Prague Stringology Conference, 2016.

T. Chhabra, S. Faro, M. O. Külekci, J. Tarhio: Engineering order-preserving pattern matching with SIMD parallelism. Software: Practice and Experience, 2016.

T. Chhabra, J. Tarhio: A filtration method for order-preserving matching. Information Processing Letters 116, 2 (2016), 71–74.

E. Giaquinta: Run-length encoded nondeterministic KMP and suffix automata. In: Proc. CIAA '15, Implementation and Application of Automata, 20th International Conference, Lecture Notes in Computer Science 9223, Springer 2015, 102–113.

T. Chhabra, E. Giaquinta, J. Tarhio: Filtration algorithms for approximate order-preserving matching. In: Proc. SPIRE '15, String Processing and Information Retrieval, 22nd International Symposium, Lecture Notes in Computer Science 9309, Springer 2015, 177–187.

T. Chhabra, S. Ghuman, J. Tarhio: Tuning algorithms for jumbled matching. In: Proc. PSC '15, 14th Prague Stringology Conference, 2015, 36–46.

T. Chhabra, M. O. Kulekci, J. Tarhio: Alternative algorithms for order-preserving matching. In: Proc. PSC '15, 14th Prague Stringology Conference, 2015, 57–66.

T. Flouri, E. Giaquinta, K. Kobert, E. Ukkonen: Longest common substrings with k mismatches Information Processing Letters 115, 6-8 (2015), 643–647.

E. Giaquinta, A. Mishra, L. Pozzi: Maximum convex subgraphs under I/O constraint for automatic identification of custom instructions IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34, 3 (2015), 483-494.

Full listing


String Algorithms
. (Last time: Spring 2016.)