Open problems in stringology. (English) Zbl 0607.68054
Combinatorial algorithms on words, Proc. NATO Adv. Res. Workshop, Maratea/Italy 1984, NATO ASI Ser., Ser. F 12, 1-8 (1985).
[For the entire collection see Zbl 0564.00027.]
The string matching problem, in its simplest form, is the following: given two strings, the pattern and the text, find all occurrences of the pattern in the text. In this paper the author surveys several open problems concerning the algorithmic aspects of combinatorics of strings. Many of these are variants, extensions or variations of the basic string matching problem. The problems are divided into four groups: string matching, generalizations of string matching, index construction and miscellaneous. The survey is useful and up-to-date.
The string matching problem, in its simplest form, is the following: given two strings, the pattern and the text, find all occurrences of the pattern in the text. In this paper the author surveys several open problems concerning the algorithmic aspects of combinatorics of strings. Many of these are variants, extensions or variations of the basic string matching problem. The problems are divided into four groups: string matching, generalizations of string matching, index construction and miscellaneous. The survey is useful and up-to-date.
Reviewer: G.Slutzki
MSC:
| 68R99 | Discrete mathematics in relation to computer science |
| 68Q45 | Formal languages and automata |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68-02 | Research exposition (monographs, survey articles) pertaining to computer science |
