CF1506C Double-ended Strings（差不多就是找最长串问题）

题目描述

You are given the strings aa and bb , consisting of lowercase Latin letters. You can do any number of the following operations in any order:

• if |a| > 0∣a∣>0 (the length of the string aa is greater than zero), delete the first character of the string aa , that is, replace aa with a_2 a_3 \ldots a_na2a3…an ;
• if |a| > 0∣a∣>0 , delete the last character of the string aa , that is, replace aa with a_1 a_2 \ldots a_{n-1}a1a2…an−1 ;
• if |b| > 0∣b∣>0 (the length of the string bb is greater than zero), delete the first character of the string bb , that is, replace bb with b_2 b_3 \ldots b_nb2b3…bn ;
• if |b| > 0∣b∣>0 , delete the last character of the string bb , that is, replace bb with b_1 b_2 \ldots b_{n-1}b1b2…bn−1 .

Note that after each of the operations, the string aa or bb may become empty.

For example, if a=a= "hello" and b=b= "icpc", then you can apply the following sequence of operations:

• delete the first character of the string aa \Rightarrow⇒ a=a= "ello" and b=b= "icpc";
• delete the first character of the string bb \Rightarrow⇒ a=a= "ello" and b=b= "cpc";
• delete the first character of the string bb \Rightarrow⇒ a=a= "ello" and b=b= "pc";
• delete the last character of the string aa \Rightarrow⇒ a=a= "ell" and b=b= "pc";
• delete the last character of the string bb \Rightarrow⇒ a=a= "ell" and b=b= "p".

For the given strings aa and bb , find the minimum number of operations for which you can make the strings aa and bb equal. Note that empty strings are also equal.

输入格式

The first line contains a single integer tt ( 1 \le t \le 1001≤t≤100 ). Then tt test cases follow.

The first line of each test case contains the string aa ( 1 \le |a| \le 201≤∣a∣≤20 ), consisting of lowercase Latin letters.

The second line of each test case contains the string bb ( 1 \le |b| \le 201≤∣b∣≤20 ), consisting of lowercase Latin letters.

输出格式

For each test case, output the minimum number of operations that can make the strings aa and bb equal.

题意翻译

你有两个字符串  a,b，你可以对这个字符串进行下面的操作：

• 如果 a  非空，删除 a 的第一个字符。
• 如果 a  非空，删除 a  的最后一个字符。
• 如果 b  非空，删除  b 的第一个字符。
• 如果 b  非空，删除 b  的最后一个字符。

求至少需要多少次操作使 a  和 b  完全相同。注意，我们认为两个空串也是完全相同的。

T  组数据。

输入输出样例

输入

5

a

a

abcd

bc

hello

codeforces

hello

helo

dhjakjsnasjhfksafasd

adjsnasjhfksvdafdser

输出  

0

2

13

3

20

题意分析；首先我们可以分析知道；我们要找一个二个串的公共最长串，然后我们把2个串的长度加起来减去公共最长串就是我们要的操作次数。具体操作看代码。

#include <bits/stdc++.h>
using namespace std;
void solve() 
{
  string a, b;
  cin >> a >> b;
  int maxk = 0;
  for (int i=0; i<a.size(); i++) 
  {
    for (int j=0; j<b.size(); j++) 
    {
      int k = 0;
      while (i+k < a.size() && j+k < b.size() && a[i+k] == b[j+k])k++;
      if (k > maxk) maxk = k;
    }
  }
  cout << a.size() + b.size() -2*maxk << endl;
}
int main() 
{
  int T;
  cin >> T;
  for (int i=1; i<=T; i++)solve();
}