(such as in text compressionactually gives rise to optimal algorithms finallyin discussing text similaritywe introduce the dynamic programming design patternwhich can be applied in some special instances to solve problem in polynomial time that appears at first to require exponential time to solve text processing at the heart of algorithms for processing text are methods for dealing with character strings character strings can come from wide variety of sourcesincluding scientificlinguisticand internet applications indeedthe following are examples of such stringsp "cgtaaactgctttaatcaaacgcs "the first stringpcomes from dna applicationsand the second stringsis the internet address (urlfor the web site that accompanies this book several of the typical 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 use the term substring of an -character string to refer to string of the form [ ] [ ] [ [ ]for some < < < that isthe string formed by the characters in from index to index jinclusive technicallythis means that string is actually substring of itself (taking and )so if we want to rule this out as possibilitywe must restrict the definition to proper substringswhich require that either or to simplify the notation for referring to substringslet us use [ jto denote the substring of from index to index jinclusive that isp[ ]= [ ] [ + [jwe use the convention that if jthen [ jis equal to the null stringwhich has length in additionin order to distinguish some special kinds of substringslet us refer to any substring of the form [ ]for < < - as prefix of pand any substring of the form [ ]for < < as suffix of for exampleif we again take to be the string of dna given abovethen "cgtaais prefix of "cgcis suffix of pand "ttaatcis (propersubstring of note that the null string is prefix and suffix of any other string to allow for fairly general notions of character stringwe typically do not restrict the characters in and to explicitly come from well-known character setlike the unicode character set insteadwe typically use the symbol to denote the character setor alphabetfrom which characters can come since most document processing algorithms are used in applications where the underlying character set is