Saturday, August 13, 2011

The programming codes for dynamic programming(c++)?

Given two strings X = x0,x1,…,xn-1 and Y = y0,y1,….,ym-1, from the alphabet set (A,C,G,T) devise an algorithm (using dynamic programming) to find the length of their longest common sub-string, that is, the largest k for which there are indices i and j with xi,xi+1, ….. xi+k = yj,yj+1 ….yj+k. For example given the two strings “A,C,C,A,T,T,G” and “A,T,T,A,C”, the longest common sub-string is “A,T,T”, k=3 for i=3, and j=0 (uming that the strings start from index 0 each). Implement the algorithm in an appropriate language. (c++)

No comments:

Post a Comment