text similarity testing common text processing problemwhich arises in genetics and software engineeringis to test the similarity between two text strings in genetics applicationthe two strings could correspond to two strands of dnawhich couldfor examplecome from two individualswho we will consider genetically related if they have long subsequence common to their respective dna sequences likewisein software engineering applicationthe two strings could come from two versions of source code for the same programand we may wish to determine which changes were made from one version to the next indeeddetermining the similarity between two strings is considered such common operation that the unix and linux operating systems come with programcalled difffor comparing text files problem the longest common subsequence there are several different ways we can define the similarity between two strings even sowe can abstract simpleyet commonversion of this problem using character strings and their subsequences given string - subsequence of is any string that is of the form ik where + that isit is sequence of characters that are not necessarily contiguous but are nevertheless taken in order from for examplethe string aaag is subsequence of the string cgataattgaga note that the concept of subsequence of string is different from the one of substring of stringdefined in section problem definition the specific text similarity problem we address here is the longest common subsequence (lcsproblem in this problemwe are given two character stringsx - and - over some alphabet (such as the alphabet { ,cgtcommon in computational geneticsand are asked to find longest string that is subsequence of both and one way to solve the longest common subsequence problem is to enumerate all subsequences of and take the largest one that is also subsequence of since each character of is either in or not in subsequencethere are potentially different subsequences of xeach of which requires (mtime to determine whether it is subsequence of thusthis brute-force approach yields an exponential-time algorithm that runs in ( nmtimewhich is very inefficient in this sectionwe discuss how to use an algorithmic design pattern called dynamic programming to solve the longest common subsequence problem much faster than this dynamic programming