公共子串计算

公共子串计算

思路：
f[i][j]表示s1 [1 ~ i] s2 [1 ~ j]中分别以s1[i] s2[j]结尾的公共子序列的长度，属性为max。
状态计算以s1[i] s2[j]是否相等划分，如果不等，f[i][j] = 0,相等，f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1)。

代码：

#include<iostream>
#include<string>
using namespace std;
const int N = 150;
int f[N][N];

int main(){
    string s1,s2;
    cin>>s1>>s2;
    int n = s1.size(),m = s2.size();
     
    //s1 = ' ' + s1,s2 = ' ' + s2;
    for(int i = 0; i <= n; i++) f[i][0] = 0;
    for(int j = 0; j <= m; j++) f[0][j] = 0;
    
    int res = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            //当前字符不相等
            f[i][j] = 0;
            //当前字符相等 f[i][j] = max(f[i][j],f[i - ][j - ] + 1)
            if(s1[i - 1] == s2[j - 1]) {
                f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1);
                res = max(res,f[i][j]);
            }
        }
    }
    cout<<res;
    return 0;
   
}