Edit Question - KnowledgeHub

Title Body

Problem: Need the Length of the LCS between two strings. The size of the strings is at most 100 characters. The alphabet is the usual DNA one, 4 characters "ACGT". The dynamic approach is not quick enough. My problem is that I am dealing with lot's and lot's of pairs (of the rank of hundreds of million as far as I can see). I believe I have decreased the calling of the LCS_length function to the minimum possible so the only other way to make my program run faster is to have a more efficient LCS_Length function. I have started off by implementing in the usual dynamic programming approach. That gives the correct answer and is hopefully implemented in properly. #define arrayLengthMacro(a) strlen(a) + 1 #define MAX_STRING 101 static int MaxLength(int lengthA, int lengthB); /* * Then the two strings are compared following a dynamic computing * LCS table algorithm. Since we only require the length of the LCS * we can get this rather easily. */ int LCS_Length(char *a, char *b) { int lengthA = arrayLengthMacro(a),lengthB = arrayLengthMacro(b), LCS = 0, i, j, maxLength, board[MAX_STRING][MAX_STRING]; maxLength = MaxLength(lengthA, lengthB); //printf("%d %d\n", lengthA, lengthB); for (i = 0; i < maxLength - 1; i++) { board[i][0] = 0; board[0][i] = 0; } for (i = 1; i < lengthA; i++) { for (j = 1; j < lengthB; j++) { /* If a match is found we allocate the number in (i-1, j-1) incremented * by 1 to the (i, j) position */ if (a[i - 1] == b[j - 1]) { board[i][j] = board[i-1][j-1] + 1; if(LCS < board[i][j]) { LCS++; } } else { if (board[i-1][j] > board[i][j-1]) { board[i][j] = board[i-1][j]; } else {

Tags (comma-separated) Cancel