[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:09:33 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

String Searching:   Introduction.

which can implement lookup Tables of `elements', e.g. numbers, words, strings, sub-strings etc. Now,  there are special algorithms (below) and data-structures for finding sub-strings of a text string:

String search


This is a very important problem, e.g. :

String search, Naive Algorithm:

To search for pat[1..m] in txt[1..n]   (NB. 1..   not 0.. )

Properties of Naive Algorithm for String search:

Rabin's Algorithm for String search

Strings   . . . Rabin's algorithm.   To compute txtHashi from txtHashi-1 in O(1)-time:

   patHash =
     (((ord(pat[1])*3+ord(pat[2]))*3+...+ord(pat[m])
     ) mod p

   txtHash1=
     (((ord(txt[1])*3+ord(txt[2]))*3+...+ord(txt[m])
     ) mod p

   txtHashi=
     ((txtHashi-1 - ord(txt[i-1])*power)*3
                  + ord(txt[i+m-1])
     ) mod p,                              where i>1
(Related to Horner's rule.)
©
L
.
A
l
l
i
s
o
n

Strings

Properties of Rabin's Algorithm

Strings

O(n) string search

Boyer Moore   String searching . . .

Key Idea: step through txt[1.. ] with a stride of `m'

[lecturer: draw diagram / example; class: take notes!]

Boyer Moore String searching

Can guarantee O(n)-time worst-case performance although the code for this guarantee is beyond this subject.

Most important: O( n / m )-time on average if m < < | alphabet |.

String:   Searching Summary.

We will see later for the Suffix-tree data structure that query, search time can be reduced to O(m) if pre-processing time is O(n),   i.e. to build the suffix-tree.

Prepare: Graph algorithms.
© L.Allison, Sunday, 28-Nov-2021 04:09:33 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/13string.shtml
Computer Science, Software Engineering, Science (Computer Science).