题意

给定两个字符串a,b,求a，b最长公共子串

思路

• 动态规划，最长的子串一定是由倒数第二长的子串加上两个串中一组相同的字符得来的
• 即：（相同时） （不同）

AC代码

#include<bits/stdc++.h>
using namespace std;
int f[5050][5050];
int main(){
    string a,b;
    while(cin >> a >> b){
        a=' '+a;
        b=' '+b;
        if(a[1]==b[1]) f[1][1]=1;
        for(int i=1;i<a.size();i++){
            for(int j=1;j<b.size();j++){
                if(a[i]==b[j])f[i][j]=1+f[i-1][j-1];
                else f[i][j]=max(f[i-1][j],f[i][j-1]);
            }
        }
        cout << f[a.size()-1][b.size()-1] << endl;    
    }
    return 0;
    
}