算法

cf1989 ABCD

https://codeforces.com/contest/1989

B最长公共子序列

		//相当于枚举以b[i]为起点遍历a的最长公共子序列
		//因为是子序列所以 ab   acccab 即使后面先取了第一个a也不影响最长长度
#include<bits/stdc++.h>
using namespace std;
void solve()
	{
	string a,b;
	int maxn=-1;
	cin>>a>>b;
	int l,r;
	int sa=a.size();
	int sb=b.size();
	for(int i=0; i<sb; i++)
		{
		l=0,r=i;
		while(l<sa&&r<sb)
			{
			if(a[l]==b[r])
				r++;
			l++;
			}
		maxn=max(maxn,r-i);
		}
	cout<<sa+sb-maxn<<endl;
	}
signed main()
	{
	int t;
	cin>>t;
	while(t--)
		solve();

	}