This C program finds the longest common sub-sequence between two strings. It implements the most famous dynamic programming algorithm.

**Dynamic programming** is a computational technique used to solve complex problems by breaking them down into smaller subproblems and solving each subproblem only once, storing the solution to each subproblem and using it to solve larger problems.

Dynamic programming algorithms are often used in computer programming to solve problems that involve optimization, such as finding the shortest path in a graph or the optimal way to arrange items in a knapsack. Examples of well-known dynamic programming algorithms include the Bellman-Ford algorithm for finding the shortest path in a weighted graph, the Knapsack algorithm for optimizing the contents of a knapsack, and the Fibonacci sequence algorithm for generating the Fibonacci sequence of numbers.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | //****** // lcs.c //** - finds the longest common sub-sequence between 2 strings //** - implements the most famous dynamic programming algorithm //** - output is a null-terminated string, so must be the input //** Notes //** - this package is provided as is with no warranty. //** - the author is not responsible for any damage caused //** either directly or indirectly by using this package. //** - anybody is free to do whatever he/she wants with this //** package as long as this header section is preserved. //** Created on 2005-01-22 by //** - Roger Zhang ([email protected]) //** Modifications //** - //** Last compiled under Linux with gcc-3 //************************** #include <stdlib.h> #include <string.h> char *lcs(char *s, char *t) { char *result; int n = strlen(s), m = strlen(t), i, j, **a; if (!n || !m) { /* empty input string */ return ""; } a = (int**)calloc(n + 1, sizeof(int*)); a[0] = (int*)calloc((n + 1) * (m + 1), sizeof(int)); for (i = a[0][0] = 0; i <= n; i++) { /* find the length */ if (!i || (a[i] = a[i - 1] + m)) { for (j = 0; j <= m; j++) { if (!i || !j) { /* initialize the base row/column */ a[i][j] = 0; } else if (s[i - 1] == t[j - 1]) { /* diagonal step */ a[i][j] = a[i - 1][j - 1] + 1; } else { /* horizontal or vertical step */ a[i][j] = a[i][j - 1] > a[i - 1][j] ? a[i][j - 1] : a[i - 1][j]; } } } else { abort(); /* memory failure */ } } if (!(i = a[n][m])) { return ""; /* no common sub-sequence */ } if (!(result = (char*)malloc(i + 1)) || (result[i] = '\0')) { abort(); /* memory allocation failed */ } while (n > 0 && m > 0) { /* back track to find the sequence */ if (s[n - 1] == t[m - 1] && m--) { result[--i] = s[--n]; } else { a[n][m - 1] >= a[n - 1][m] ? m-- : n--; } } free(a[0]); free(a); return result; } |

This program is last compiled under Linux using gcc-3 compiler.

*This package is provided as is with no warranty. The author is not responsible for any damage caused either directly or indirectly by using this package. Anybody is free to do whatever he/she wants with this package as long as this header section is preserved.Created on 2005-01-22 by Roger Zhang ([email protected])*