最长公共子序列

2013-02-12 14:22:23   最后更新: 2015-08-06 23:30:25   访问数量:733




最长公共子序列是很多领域的经典问题,其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的

最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。

 

 

/* * file: main.c * author: 龙泉居士 * date: 2013-02-12 14:22 */ #include <stdio.h> #include <malloc.h> #include <string.h> typedef enum Direction { same, left, up } Direction; typedef struct Node { int value; Direction d; } Node; void getLCS (char *a, char *b) { if (a==NULL || b==NULL) { printf ("param error\n"); return; } int i, j; Node **narray = (Node*)malloc(sizeof(Node*)*(strlen(a)+1)*(strlen(b)+1)); for (i=0; i<=strlen(a); ++i) for (j=0; j<=strlen(b); ++j) { Node *n = (Node *)malloc(sizeof(Node)); if (i==0 || j==0) n->value = 0; else if (a[i-1] == b[j-1]) { n->value = narray[(i-1)*(strlen(b)+1)+j-1]->value + 1; n->d = same; } else if (narray[(i-1)*(strlen(b)+1)+j]->value >= narray[i*(strlen(b)+1)+j-1]->value) { n->d = up; n->value = narray[(i-1)*(strlen(b)+1)+j]->value; } else { n->d = left; n->value = narray[i*(strlen(b)+1)+j-1]->value; } narray[i*(strlen(b)+1)+j] = n; } i = strlen(a); j = strlen(b); printf ("The length of LCS is: %d\n", narray[i*(strlen(b)+1)+j]->value); char *res = (char *)malloc(sizeof(char)*narray[i*(strlen(b)+1)+j]->value); int k = narray[i*(strlen(b)+1)+j] -> value-1; while (1) { switch (narray[i*(strlen(b)+1)+j]->d) { case same: --i; --j; res[k] = a[i]; --k; break; case up: --i; break; case left: --j; break; } if (i<=0 || j<=0) break; } printf ("%s\n", res); for (i=strlen(a); i>=0; --i) for (j=strlen(b); j>=0; --j) free(narray[i*(strlen(b)+1)+j]); free(narray); free(res); } int main () { char a[20], b[20]; printf ("Please input the string A:\n"); scanf ("%s", a); printf ("Please input the string B:\n"); scanf ("%s", b); getLCS (a, b); return 0; }

 

 






读书笔记      技术帖      算法      算法导论      c语言      龙潭书斋      lcs      最长公共子序列      动态规划      字符串      子字符串     


京ICP备15018585号