字符串

C. Double-ended Strings（最长公共子串）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }

const int N = 20 + 7;
const int INF = 0x3f3f3f3f;
ll res[N][N];
int main(){
    int t = read();
    while(t--){
        string a,b;
        cin>>a>>b;
        ll ans = 0;
        memset(res, 0 ,sizeof(res));
        for(int i = 1; i <= a.size() ; i++){
            for(int j = 1 ; j <= b.size() ; j++){
                if(a[i - 1] == b[j - 1]){
                    res[i][j] = res[i-1][j-1] + 1;
                    ans = max(res[i][j] , ans);
                }
            }
        }
        cout<<a.size() - ans + b.size() - ans<<endl;
    }
    return 0;
}