我的解題思路：

創(chuàng)新互聯(lián)公司是一家專業(yè)提供洛龍企業(yè)網(wǎng)站建設(shè),專注與做網(wǎng)站、網(wǎng)站制作、H5開發(fā)、小程序制作等業(yè)務(wù)。10年已為洛龍眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計公司優(yōu)惠進(jìn)行中。

 生成動態(tài)規(guī)劃表，即大小為M*N的矩陣dp（M和N分別是兩個字符串的長度）；

求dp[i][j]過程：

 1.矩陣第一列即dp[0~M-1][0],對某一個位置（i，0）來說，如果str1[i]==str2[0],令dp[i][0]=1,.否則令dp[i][0]=0;

 2.矩陣第一行即dp[0][0~N-1]，對某一個位置（0，j）來說，如果str1[0]==str2[j],令dp[0][j]=1,.否則令dp[i][0]=0;

 3.其余位置按照從左到右，從上到下位置計算，dp[i][j]的值只可能有兩種情況：

    a.如果str1[i]!=str2[j],說明在必須把str1[i]和str2[j]當(dāng)做公共子串的最后一個字符是不可能的，令dp[i][j]=0;

    b.如果str1[i]==str2[j],說明str1[i]和str2[j]可以當(dāng)做公共子串的最后一個字符，dp[i][j]=dp[i-1][j-1]+1;

生成動態(tài)規(guī)劃表后，表里面大的數(shù)字就是公共子串的長度

下面是具體的代碼：

#include <iostream>

#include <string>

using namespace std;

int dp[8][8] = { 0 };//二維矩陣大小自己定義，保證能容下字符串就行

void initdp(char *str1, char *str2)

{

int len1 = strlen(str1);

int len2 = strlen(str2);

for (int i = 0; i < len1; i++)

{

if (str1[i] == str2[0])

{

dp[i][0] = 1;

}

}

for (int j = 1; j < len2; j++)

{

if (str2[j] == str1[0])

{

dp[0][j] = 1;

}

}

for (int i = 1; i < len1; i++)

{

for (int j = 1; j < len2; j++)

{

if (str1[i] == str2[j])

{

dp[i][j] = dp[i - 1][j - 1] + 1;

}

}

}

}

void MaxChar(char *str1, char *str2)

{

int len1 = strlen(str1);

int len2 = strlen(str2);

int max = 0;

int end = 0;

for (int i = 0; i < len1; i++)

{

for (int j = 0; j < len2; j++)

{

if (dp[i][j]>max)

{

max = dp[i][j];

end = i;

}

}

}

for (int i = end - max+1; i <= end; ++i)

{

printf("%c", str1[i]);

}

printf("\n");

}

int main()

{

char *str1 = "ab123cd";

char *str2 = "db1234cg";

initdp(str1, str2);

MaxChar(str1, str2);

return 0;

}

如果哪位大神還有更好的方法請給小生說下，謝謝啦

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

當(dāng)前文章：最長公共子串問題-創(chuàng)新互聯(lián)
本文來源：http://www.rwnh.cn/article20/cciijo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、商城網(wǎng)站、標(biāo)簽優(yōu)化、企業(yè)網(wǎng)站制作、響應(yīng)式網(wǎng)站、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)