Maximum Subsequence Contest Problem. Dynamic Programming.

MaximumSubsequence.c

#include <stdio.h>

#define N 256
#define L 1000000
#define nstr 100
/*
 * 'str1' and 'str2' are two temporary variables where we store strings to process
 */
char str1[N];
char str2[N];
/*
 * 'result' is the variable where we store the intermediate and final result.
 * It eventually contains the LCS from which we deduce its length.
 */
char result[N];
/*
 * temp is the variable that contains the final LCS result after comparing two
 * and only two strings.
 */
char temp[N];
/*
 * str is the array of strings where we store strings inputted from the keyboard.
 */
char str[nstr][L];
/*
 * c is the matrix where we store the matches between two characters.
 */
unsigned short c[N][N];
/*
 * max returns the bigger value out of the two arguments.
 */
short max( short , short );
/*
 * strrev reverses the string passed as an argument.
 */
void strrev( char * );

int main() {
	/*
	 * - nbr is the integer that indicates the number of strings to input.
	 * - x is a used in this program as an iterator variable.
	 */
	unsigned short nbr, x;
	/*
	 * n stores the length of the first string that is being processed.
	 * m stores the length of the second string that is being processed.
	 */
	unsigned short m, n;
	/*
	 * - i and j are used as loops indices.
	 * - len is used to concatenate the elements that constitute the LCS.
	 */
	short i, j, len ;
	do{
		scanf("%d", &nbr);
		fflush(stdin);
		if(nbr == 0) break;
		x = nbr;
		i=0;
		do {
			gets(str[i ++]);
			x --;
		} while( x > 0 );
		x = 1;
		strcpy(result, str[0]);
		do {
			len = 0;
			strcpy(str1, result);
			strcpy(str2, str[x]);
			/*
			 * Begin:	LCS Dynamic Programming solution
			 *
			 * -	O(m*n) since each c[i,j] is calculated in constant time, and there are m * n elements in the array. (source: course material, ch7.ppt)
			 */			
			m = strlen(str1);
			n = strlen(str2);
			
			for (i = 0; i <= m ; i ++ ) {
				c[ i ][ 0 ] = 0;
			}
			for (i = 0; i <= n ; i ++ ) {
				c[ 0 ][ i ] = 0;
			}
			for (i = 1 ; i <= m ; i ++ ) {
				for (j = 1 ; j <= n ; j ++ ) {
					if ( str1[ i - 1 ] == str2[ j - 1 ] )
						c[ i ][ j ] = c[ i - 1 ][ j - 1] + 1;
					else
						c[ i ][ j ] = max( c[ i - 1 ][ j ], c[ i ][ j - 1 ] );
				}
			}
			for (i = m , j = n ; i >= 0 && j >= 0 ;  ) {
				if ( c[ i ][ j ] == c[ i ][ j - 1 ]) {
						j --;
				} else {
					if ( c[ i ][ j ] == c[ i - 1 ][ j ]) {
						i --;
					} else {
						if ( c[ i ][ j ] == c[ i - 1 ][ j - 1 ] + 1) {
							temp[ len ++ ] = str1[ i - 1 ];
							i --; j --;
						}
					}
				}
			}
			temp[ len ] = '\0';
			strrev(temp);
			/*
			 * End:		LCS Dynamic Programming solution
			 */			
			strcpy(result, temp);
			x++;
		} while ( strcmp(str1, "") && strcmp(str2, "") && x < nbr );
		printf("%d\n\n", strlen(result));
//		puts("\n");
		nbr--;
	}while(nbr);
	return 0;
}

short max( short a , short b ) {
	if ( a > b ) return a;
	return b;
}

void strrev(char *p) {
  char *q = p;
  while(q && *q) ++q;
  for(--q; p < q; ++p, --q)
    *p = *p ^ *q,
    *q = *p ^ *q,
    *p = *p ^ *q;
}