/*目標：輸出兩個字串的所有公共最長子序列

date:09-11-26

BY:zggxjxcgx

演算法：判斷較短串是否為較長串的子序列，如果是則得到結果；

*/

#include

#include

intdep=0;/*較短串的長度*/

intdepflag=0;/*下一步要探測的深度*/

intlastflag=0;/*是否找到匹配子序列，1為找到*/

intcount=0;/*目標結果的個數*/

intmystrcmp(char*s1,char*s2)/*判斷s2是否為s1的子串*/

{while(*s1*s2)

if(*s2=="#")s2++;

elseif(*s2==*s1){s1++;s2++;}

elses1++;

while(*s2=="#")s2++;

if(*s2=="\0")return1;

return0;

}

voidpristr(char*str)/*列印最長子序列*/

{if(0==count++)printf("\n公共最長子序列：\n");

printf("%2d:",count);

while(*str)

{if(*str!="#")

printf("%c",*str);

str++;

}

printf("\n");

}

/*遞迴函式求最長子序列。start控制下一個要檢測的字元,deptemp控制遞迴的深度,first為"s"表示第一層遞迴*/

intfun(char*str1,char*str2,char*start,intdeptemp,charfirst)

{inti=0,j=0;

char*s,cback;

do

{s=start;

if("s"==first)deptemp=depflag;/*在第一層設定遞迴深度*/

while(*s)

{if(*s=="#"){s++;continue;}

if(mystrcmp(str1,str2)){pristr(str2);lastflag=1;}/*找到匹配，將lastflag設為1，在完成深度為deptemp+1的探測（找到所有匹配）後退出遞迴*/

*s=cback;s++;/*還原該位置的字元，以便下次進行探測*/

}

}while(depflag