  Strings form a fundamental data type in computer systems. String searching
has been extensively studied since the inception of computer science.
Increasingly many applications have to deal with imprecise strings or strings
with fuzzy information in them. String matching becomes a probabilistic event
when a string contains uncertainty, i.e. each position of the string can have
different probable characters with associated probability of occurrence for
each character. Such uncertain strings are prevalent in various applications
such as biological sequence data, event monitoring and automatic ECG
annotations. We explore the problem of indexing uncertain strings to support
efficient string searching. In this paper we consider two basic problems of
string searching, namely substring searching and string listing. In substring
searching, the task is to find the occurrences of a deterministic string in an
uncertain string. We formulate the string listing problem for uncertain
strings, where the objective is to output all the strings from a collection of
strings, that contain probable occurrence of a deterministic query string.
Indexing solution for both these problems are significantly more challenging
for uncertain strings than for deterministic strings. Given a construction time
probability value $\tau$, our indexes can be constructed in linear space and
supports queries in near optimal time for arbitrary values of probability
threshold parameter greater than $\tau$. To the best of our knowledge, this is
the first indexing solution for searching in uncertain strings that achieves
strong theoretical bound and supports arbitrary values of probability threshold
parameter. We also propose an approximate substring search index that can
answer substring search queries with an additive error in optimal time. We
conduct experiments to evaluate the performance of our indexes.
