学步园

求str1和str2的最长公共子序列的长度。定义状态pf[i][j]表示分别以str1[i]，str2[j]结尾的连续公共子串的长度。所以对于pf[i+1][j+1]，有两种情况：
1. str1[i+1] != str2[j+1]，则pf[i+1][j+1] = 0；
2. str1[i+1]  = str2[j+1]，则pf[i+1][j+1] = pf[i][j] + 1；
代码如下：#include <iostream><br /> #include <string.h></p> <p>int maxCommStr(char* str1, char* str2)<br /> {<br /> int len1, len2, i, j, max = 0, end = 0;<br /> len1 = strlen(str1);<br /> len2 = strlen(str2);</p> <p> int** pf = new int*[len1]; //根据字符串长度分配一个二维数组</p> <p> for (i=0; i<len1; i++)<br /> {<br /> pf[i] = new int[len2];<br /> }</p> <p> for (i=0; i<len1; i++)<br /> {<br /> for (j=0; j<len2; j++)<br /> {<br /> pf[i][j] = 0; //数组初始化<br /> }<br /> }</p> <p> for (i=0; i<len1; i++)<br /> {<br /> for (j=0; j<len2; j++)<br /> {<br /> if (i == 0 || j == 0) //处理以第一个字符结尾(长度为1)的情况<br /> {<br /> if (str1[i] == str2[j])<br /> {<br /> pf[i][j] = 1;<br /> if (pf[i][j] > max)<br /> {<br /> max = pf[i][j];<br /> end = i;<br /> }<br /> }<br /> else<br /> {<br /> pf[i][j] = 0;<br /> }<br /> }<br /> else<br /> {<br /> if (str1[i] == str2[j])<br /> {<br /> pf[i][j] = pf[i-1][j-1] + 1;<br /> if (pf[i][j] > max)<br /> {<br /> max = pf[i][j];<br /> end = i;<br /> }<br /> }<br /> else<br /> {<br /> pf[i][j] = 0;<br /> }<br /> }<br /> }<br /> }</p> <p> for (i=0; i<len1; i++) //清除内存<br /> {<br /> delete pf[i];<br /> }</p> <p> delete pf;</p> <p> char* ret = new char[max+1];<br /> memcpy(ret, str1+end-max+1, max);<br /> ret[max] = '/0';<br /> std::cout << ret << std::endl;</p> <p> return max;<br /> }<br /> int main()<br /> {<br /> char* str1 = "blog.csdn.netc";<br /> char* str2 = "blog.aaaa.netc";</p> <p> std::cout << maxCommStr(str1, str2) << std::endl;<br /> return 0;<br /> }