Browse/search for people

Publication - Dr Raphael Clifford

    Dictionary matching in a stream


    Clifford, R, Fontaine, A, Porat, E, Sach, B & Starikovskaya, T, 2015, ‘Dictionary matching in a stream’. in: Algorithms – ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings. Springer Verlag, pp. 361-372


    We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our dictionary occurs in the stream. We present a randomised algorithm which takes O(log log(k + m)) time per arriving character and uses O(k log m) words of space, where k is the number of strings in the dictionary and m is the length of the longest string in the dictionary.

    Full details in the University publications repository