学步园

(min (m, n))空间求出最长公共子序列的长度.这个问题琢磨了好久,终于还是睾出来了.   实现的思想就是,从两个串中选出一个较长的串.用另外一个串的所有,同较长串的当前值比较.只记录最大的长度,最终完成.   说的,比较简单.研究过程,还算一般.全下来大约4小时.是慢还是快?貌似很慢啊,希望自己今后养成高速解决问题的习惯吧.   还有啊,网吧是在是太吵了...

// 15-4-4.cpp -- 2011-06-18-15.33<br /> // Completeed at 2011-06-19-10.26<br /> #include "stdafx.h"<br /> #include <iostream></p> <p>int maxLenth (const char * const strA, const char * const strB) ;</p> <p>int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> char * strA = " ABCDBABCBABDA", * strB = " ABDBAABABCBDBABCDABA" ;<br /> std ::cout << maxLenth(strA, strB) << std ::endl ;</p> <p> return 0 ;<br /> }<br /> // Assume aSize <= bSize<br /> int maxLenth (const char * const strA, const char * const strB)<br /> {<br /> int aSize = strlen(strA) ;<br /> int bSize = strlen(strB) ;<br /> int * maxLenth = new int[aSize] ;</p> <p> if (!maxLenth)<br /> return -1 ;<br /> for (int i = 0; i < aSize; ++i)<br /> maxLenth[i] = 0 ;<br /> for (int i = 0; i < bSize; ++i)<br /> {<br /> if (strB[i] == strA[0])<br /> maxLenth[0] = 1 ;<br /> else<br /> maxLenth[0] = 0 ;<br /> for (int j = 1; j < aSize; ++j)<br /> {<br /> if (strB[i] == strA[j])<br /> {<br /> int max = 0 ;<br /> for (int k = j - 1; k >= 0; --k)<br /> {<br /> if (maxLenth[k] < i + 1 && maxLenth[k] > max)<br /> max = maxLenth[k] ;<br /> }<br /> if (max == maxLenth[j])<br /> maxLenth[j] = maxLenth[j] + 1 ;<br /> else if (max + 1 < maxLenth[j])<br /> continue ;<br /> else maxLenth[j] = max + 1 ;<br /> }<br /> }<br /> }<br /> int max = maxLenth[aSize - 1] ;<br /> delete []maxLenth ;</p> <p> return max ;<br /> }<br />