@inproceedings{77484c05f7cf4edca327fd064b1c5534,
title = "Work-time optimal parallel prefix matching",
abstract = "Consider the prefix matching problem: Given a pattern P of length m and a text T of length n, find for all positions i in T the longest prefix of P starting at i. We present a parallel algorithm for the prefix matching problem over general alphabets whose text search takes optimal O(α(m)) time and preprocessing takes optimal O(log log m) time, where α(m) is the inverse Ackermann function. An Ω(log log m) lower bound for the prefix matching problem is implied by the same lower bound for string matching. However, the lower bound is applied only to preprocessing of the pattern and the searching phase can be faster. We prove an Ω(α(m)) lower bound for any linear-work searching phase. Therefore our algorithm is work-time optimal in both preprocessing and text search. The idea of leftmost witnesses is introduced to obtain the algorithm.",
author = "Leszek G{\c a}sieniec and Kunsoo Park",
year = "1994",
month = jan,
day = "1",
language = "English (US)",
isbn = "9783540584346",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "471--482",
editor = "{van Leeuwen}, Jan",
booktitle = "Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings",
note = "2nd Annual European Symposium on Algorithms, ESA 1994 ; Conference date: 26-09-1994 Through 28-09-1994",
}