License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2018.10
URN: urn:nbn:de:0030-drops-88017
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8801/
Boldi, Paolo ;
Vigna, Sebastiano
Kings, Name Days, Lazy Servants and Magic
Abstract
Once upon a time, a king had a very, very long list of names of his subjects. The king was also a bit obsessed with name days: every day he would ask his servants to look the list for all persons having their name day. Reading every day the whole list was taking an enormous amount of time to the king's servants. One day, the chancellor had a magnificent idea: he wrote a book with instructions. The number of pages in the book was equal to the number of names, but following the instructions one could find all people having their name day by looking at only a few pages - in fact, as many pages as the length of the name - and just glimpsing at the list. Everybody was happy, but in time the king's servants got lazy: when the name was very long they would find excuses to avoid looking at so many pages, and some name days were skipped. Desperate, the king made a call through its reign, and a fat sorceress answered. There was a way to look at much, much fewer pages using an additional magic book. But sometimes, very rarely, it would not work (magic does not always work). The king accepted the offer, and name days parties restarted. Only, once every a few thousand years, the magic book fails, and the assistants have to go by the chancellor book. So the parties start a bit later. But they start anyway.
BibTeX - Entry
@InProceedings{boldi_et_al:LIPIcs:2018:8801,
author = {Paolo Boldi and Sebastiano Vigna},
title = {{Kings, Name Days, Lazy Servants and Magic}},
booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)},
pages = {10:1--10:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-067-5},
ISSN = {1868-8969},
year = {2018},
volume = {100},
editor = {Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8801},
URN = {urn:nbn:de:0030-drops-88017},
doi = {10.4230/LIPIcs.FUN.2018.10},
annote = {Keywords: Suffix trees, suffix arrays, z-fast tries, prefix search}
}
|
Keywords: |
|
Suffix trees, suffix arrays, z-fast tries, prefix search |
|
Collection: |
|
9th International Conference on Fun with Algorithms (FUN 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.06.2018 |
