#include
#include

char?a[500]b[500];
char?num[501][501];?///記錄中間結果的數組
char?flag[501][501];????///標記數組，用于標識下標的走向，構造出公共子序列

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]）???///注意這里的下標是i-1與j-1
????????????{
????????????????num[i][j]=num[i-1][j-1]+1;
????????????????flag[i][j]=1;??///斜向下標記
????????????}
????????????else?if（num[i][j-1]>num[i-1][j]）
????????????{
????????????????num[i][j]=num[i][j-1];flag[i][j]=2;??///向右標記
????????????}
????????????else
????????????{
????????????????num[i][j]=num[i-1][j];flag[i][j]=3;??///向下標記
????????????}
????????}
????}
}

void?getLCS（）
{

????char?res[500];
????int?i=strlen（a）;
????int?j=strlen（b）;
????int?k=0;????///用于保存結果的數組標志位
????while（i>0?&&?j>0）
????{
????????if（flag[i][j]==1）???///如果是斜向下標記
????????{
????????????res[k]=a[i-1];k++;i--;j--;
????????}
????????else?if（flag[i][j]==2）??///如果是斜向右標記
????????????j--;
????????else?if（flag[i][j]==3）??///如果是斜向下標記
????????????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））;?//用時間做種，每次產生隨機數不一樣
????printf（“兩個序列的字母個數：“）;
????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‘?;?//產生字母的隨機數
????????fprintf（fp“%c?“a[i]）;
????}
????fprintf（fp“\n“）;

????for?（i=0;?i????{
????????b[i]?=??rand（）?%4?+?‘a‘?;?//產生字母的隨機數
????????fprintf（fp“%c?“b[i]）;
????}
????fprintf（fp“\n“）;
????fclose（fp）;
????printf（“隨機產生的兩個序列為：\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;
}

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