$$公共子串$$

Description

設(shè)有A、B兩個(gè)字符串，找出A、B共同子串，每個(gè)字符串無相同字符，可以不連續(xù)，但順序不能顛倒。

Input

第一行字符串A

第二行字符串Ｂ

Output

最長公共子串的長度.

Sample Input

abcfbc

abfcab

Sample Output

4

解題方法

用i和j來枚舉A和B的當(dāng)前字符，動(dòng)態(tài)轉(zhuǎn)移方程如下

$$f[i][j]\{\begin{array}{cc}max(f[i][j],f[i?1][j?1]+1)& a[i]=b[j]\\ max(f[i?1][j],f[i][j?1])& a[i]?=b[j]\end{array}$$

#include<cstdio> #include<iostream> #include<cstring> #include<string> using namespace std; int n,m,f[255][255]; string a,b; int main() {getline(cin,a);getline(cin,b);n=a.size();m=b.size();a=' '+a;b=' '+b;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);//動(dòng)態(tài)轉(zhuǎn)移方程if (a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);//判斷當(dāng)前字符是否相同}printf("%d",f[n][m]); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【动态规划】公共子串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。