#include
#include

char?a[500]b[500];
char?num[501][501];?///記錄中間結(jié)果的數(shù)組
char?flag[501][501];????///標(biāo)記數(shù)組，用于標(biāo)識(shí)下標(biāo)的走向，構(gòu)造出公共子序列

void?LCS（）
{
????int?ij;
????for（i=1;i<=strlen（a）;i++）
????{
????????for（j=1;j<=strlen（b）;j++）
????????{
????????????if（a[i-1]==b[j-1]）???///注意這里的下標(biāo)是i-1與j-1
????????????{
????????????????num[i][j]=num[i-1][j-1]+1;
????????????????flag[i][j]=1;??///斜向下標(biāo)記
????????????}
????????????else?if（num[i][j-1]>num[i-1][j]）
????????????{
????????????????num[i][j]=num[i][j-1];flag[i][j]=2;??///向右標(biāo)記
????????????}
????????????else
????????????{
????????????????num[i][j]=num[i-1][j];flag[i][j]=3;??///向下標(biāo)記
????????????}
????????}
????}
}

void?getLCS（）
{

????char?res[500];
????int?i=strlen（a）;
????int?j=strlen（b）;
????int?k=0;????///用于保存結(jié)果的數(shù)組標(biāo)志位
????while（i>0?&&?j>0）
????{
????????if（flag[i][j]==1）???///如果是斜向下標(biāo)記
????????{
????????????res[k]=a[i-1];k++;i--;j--;
????????}
????????else?if（flag[i][j]==2）??///如果是斜向右標(biāo)記
????????????j--;
????????else?if（flag[i][j]==3）??///如果是斜向下標(biāo)記
????????????i--;
????}
??printf（“最長公共子序列：\n“）;
????for（i=k-1;i>=0;i--）printf（“%c“res[i]）;
}

int?main（）
{
????int?in;

????FILE?*fp;
????char?number;
????srand（（unsigned）?time（NULL））;?//用時(shí)間做種，每次產(chǎn)生隨機(jī)數(shù)不一樣
????printf（“兩個(gè)序列的字母?jìng)€(gè)數(shù)：“）;
????scanf（“%d“&n）;
????fp=fopen（“input.txt““w“）;
????if（fp==NULL）
????{
????????printf（“open?file?failed\n“）;
????????return?-1;
????}

????for?（i=0;?i????{
????????a[i]?=rand（）?%?4?+?‘a(chǎn)‘?;?//產(chǎn)生字母的隨機(jī)數(shù)
????????fprintf（fp“%c?“a[i]）;
????}
????fprintf（fp“\n“）;

????for?（i=0;?i????{
????????b[i]?=??rand（）?%4?+?‘a(chǎn)‘?;?//產(chǎn)生字母的隨機(jī)數(shù)
????????fprintf（fp“%c?“b[i]）;
????}
????fprintf（fp“\n“）;
????fclose（fp）;
????printf（“隨機(jī)產(chǎn)生的兩個(gè)序列為：\n“）;
????for?（i=0;?i????{
????????printf（“%c?“a[i]）;
????}
????printf（“\n“）;

????for?（i=0;?i????{
????????printf（“%c?“b[i]）;
????}
????printf（“\n“）;

????memset（num0sizeof（num））;
????memset（flag0sizeof（flag））;
????LCS（）;
????printf（“長度：%d\n“num[strlen（a）][strlen（b）]）;
????getLCS（）;
????return?0;
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????文件????????2004??2016-12-05?12:09??最長公共子序列\(zhòng)input.txt
?????文件????????2274??2016-12-05?15:18??最長公共子序列\(zhòng)最長公共子序列.c
?????文件???????31523??2016-12-05?12:22??最長公共子序列\(zhòng)最長公共子序列.exe
?????文件????????3400??2016-12-05?12:22??最長公共子序列\(zhòng)最長公共子序列.o
?????文件???????10633??2016-12-05?12:11??最長公共子序列\(zhòng)測(cè)試用例.xlsx
?????文件???????76319??2016-12-05?15:17??最長公共子序列\(zhòng)說明+流程圖.docx
?????目錄???????????0??2019-01-06?15:47??最長公共子序列\(zhòng)