notations for strings and the python str class we use character strings as model for text when discuss algorithms for text processing character strings can come from wide variety of sourcesincluding scientificlinguisticand internet applications indeedthe following are examples of such stringss "cgtaaactgctttaatcaaacgct "the first stringscomes from dna applicationsand the second stringt is the internet address (urlfor the publisher of this book we refer to appendix for an overview of the operations supported by python' str class to allow fairly general notions of string in our algorithm descriptionswe only assume that characters of string come from known alphabetwhich we denote as for examplein the context of dnathere are four symbols in the standard alphabets { ,cgt this alphabet canof coursebe subset of the ascii or unicode character setsbut it could also be something more general although we assume that an alphabet has fixed finite sizedenoted as | |that size can be nontrivialas with python' treatment of the unicode alphabetwhich allows for more than million distinct characters we therefore consider the impact of |sin our asymptotic analysis of text-processing algorithms several string-processing operations involve breaking large strings into smaller strings in order to be able to speak about the pieces that result from such operationswe will rely on python' indexing and slicing notations for the sake of notationwe let denote string of length in that casewe let [jrefer to the character at index for < < we let notation [ :kfor < < < denote the slice (or substringof consisting of characters [jup to and including [ - ]but not [kby this definitionnote that substring [ mhas length and that substring [ :jis trivially the null stringhaving length in accordance with python conventionsthe substring [ :kis also the null string when in order to distinguish some special kinds of substringslet us refer to any substring of the form [ :kfor < < as prefix of ssuch prefix results in python when the first index is omitted from slice notationas in [:ksimilarlyany substring of the form [ :nfor < < is suffix of ssuch suffix results in python when the second index is omitted from slice notationas in [ :for exampleif we again take to be the string of dna given abovethen "cgtaais prefix of "cgcis suffix of sand "cis both prefix and suffix of note that the null string is prefix and suffix of any string