最长公共子序列_第4页

　　while(1)

　　{if(i==0││j==0)   break;

　　if(b[i][j]== '\\ '){

　　temp[h++]=x[i];   //反序记录最长公共子序列到temp中

　　i=i-1,j=j-1;

　　}

　　else

　　if(b[i][j]== '│ ')

　　i=i-1;

　　else

　　j=j-1;}

　　cout < < "\nx[ " <

　　for(i=h-1;i> =0;i--)   //格式化输出最长公共子序列

　　if(i==h-1)

　　if(h==1)

　　cout < < "LCS: < " <

　　else

　　cout < < "LCS: < " <

　　else

　　if(i==0)

　　cout < < ", " <

　　else

　　cout < < ", " <

　　cout < < "\n " <

　　}

　　三、运算结果

　　其实它的最长公共子序列不止一个，这里只输出了其中的一个。

　　四、总结分析

　　在这个具体的算法中，还有可以改进的地方，比如在具体的求最大公共子序列中，可以不必要MAX的宏定义，只需将各数组设为具体的长度就可以节约不少的空间，大大降低程序的空间复杂度，但是为了键盘输入任意字符串，牺牲了很多的内存空间。在键盘输入字符串时，可以不用循环赋值，直接用 cin> > x;cin> > y;这样就可以将这部分的时间复杂度从O(m+n)降到O(2)，但有一个相关的问题没解决，所以我没这样赋值。程序总的时间复杂度为：O(mn+3m+ 3n).