Ideone.com

download

copy

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi  vector<int>
#define pb  push_back
#define mp  make_pair
#define ALL(x) x.begin(),x.end()
#define M(a,x) memset(a,x,sizeof(a))
#define sci(x) scanf("%d",&x);
#define scl(x) scanf("%lld",&x);
#define scs(x) scanf("%s",x);
#define print(x) printf("%d",x);
#define nl printf("\n")
#define fr first
#define se second
#define printl(x) printf("%lld",x)
#define F(i,a,n) for(int i=a;i<n;i++)
#define INF 100000000000000000LL
#define LL long long
 
const int N = 1e3+5;
int dp1[N][N];
int dp2[N][N];
int LCS1(string x,string y) {
  int n = x.size();
  int m = y.size();
  for(int i=0;i<=n;i++) {
    for(int j=0;j<=m;j++) {
      if(i==0 || j==0) {
        dp1[i][j] = 0;
      }
      else if(x[i-1] == y[j-1])  {
        dp1[i][j] =1+dp1[i-1][j-1];
      }
      else {
        dp1[i][j]= max(dp1[i-1][j],dp1[i][j-1]);
      }
    }
  }
  return dp1[n][m];
}
int LCS2(string x,string y) {
  int n = x.size();
  int m = y.size();
  for(int i=0;i<=n;i++) {
    for(int j=0;j<=m;j++) {
      if(i==0 || j==0) {
        dp2[i][j] = 0;
      }
      else if(x[i-1] == y[j-1])  {
        dp2[i][j] =1+dp2[i-1][j-1];
      }
      else {
        dp2[i][j]= max(dp2[i-1][j],dp2[i][j-1]);
      }
    }
  }
  return dp2[n][m];
}
bool mark1[27];
bool mark2[27];
int main() {
  int t;sci(t);
  while(t--) {
    M(mark1,0);
    M(mark2,0);
    string a,b,c,d;
    cin >> a >> b;
    c = a;
    reverse(c.begin(),c.end());
    d = b;
    reverse(d.begin(),d.end());
    int len1 = LCS1(a,c);
    int len2 = LCS2(b,d);
    if(len1%2 && len2%2) {
      int temp = (len1-1)/2;
      for(int i=0;i<a.size();i++) {
        if(dp1[i][a.size()-1-i] == temp) {
          mark1[a[i]-'a']=true;
        }
      }
      int temp2 = (len2-1)/2;
      for(int i=0;i<b.size();i++) {
        if(dp2[i][b.size()-1-i] == temp2) {
          mark2[b[i]-'a']=true;
        }
      }
      bool flag = false;
      for(int i=0;i<26;i++) {
        if(mark1[i] && (mark1[i] == mark2[i])) {
          flag = true;
          break;
        }
      }
      if(flag) {
        cout<<len1+len2<<endl;
      }
      else {
        cout<<len1+len2-1<<endl;
      }
    }
    else {
      cout<<len1+len2<<endl;
    }
  }
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKI2RlZmluZSBwaWkgcGFpcjxpbnQsIGludD4KI2RlZmluZSBwbGwgcGFpcjxsb25nIGxvbmcsIGxvbmcgbG9uZz4KI2RlZmluZSB2aSAgdmVjdG9yPGludD4KI2RlZmluZSBwYiAgcHVzaF9iYWNrCiNkZWZpbmUgbXAgIG1ha2VfcGFpcgojZGVmaW5lIEFMTCh4KSB4LmJlZ2luKCkseC5lbmQoKQojZGVmaW5lIE0oYSx4KSBtZW1zZXQoYSx4LHNpemVvZihhKSkKI2RlZmluZSBzY2koeCkgc2NhbmYoIiVkIiwmeCk7CiNkZWZpbmUgc2NsKHgpIHNjYW5mKCIlbGxkIiwmeCk7CiNkZWZpbmUgc2NzKHgpIHNjYW5mKCIlcyIseCk7CiNkZWZpbmUgcHJpbnQoeCkgcHJpbnRmKCIlZCIseCk7CiNkZWZpbmUgbmwgcHJpbnRmKCJcbiIpCiNkZWZpbmUgZnIgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBwcmludGwoeCkgcHJpbnRmKCIlbGxkIix4KQojZGVmaW5lIEYoaSxhLG4pIGZvcihpbnQgaT1hO2k8bjtpKyspCiNkZWZpbmUgSU5GIDEwMDAwMDAwMDAwMDAwMDAwMExMCiNkZWZpbmUgTEwgbG9uZyBsb25nCgpjb25zdCBpbnQgTiA9IDFlMys1OwppbnQgZHAxW05dW05dOwppbnQgZHAyW05dW05dOwppbnQgTENTMShzdHJpbmcgeCxzdHJpbmcgeSkgewogIGludCBuID0geC5zaXplKCk7CiAgaW50IG0gPSB5LnNpemUoKTsKICBmb3IoaW50IGk9MDtpPD1uO2krKykgewogICAgZm9yKGludCBqPTA7ajw9bTtqKyspIHsKICAgICAgaWYoaT09MCB8fCBqPT0wKSB7CiAgICAgICAgZHAxW2ldW2pdID0gMDsKICAgICAgfQogICAgICBlbHNlIGlmKHhbaS0xXSA9PSB5W2otMV0pICB7CiAgICAgICAgZHAxW2ldW2pdID0xK2RwMVtpLTFdW2otMV07CiAgICAgIH0KICAgICAgZWxzZSB7CiAgICAgICAgZHAxW2ldW2pdPSBtYXgoZHAxW2ktMV1bal0sZHAxW2ldW2otMV0pOwogICAgICB9CiAgICB9CiAgfQogIHJldHVybiBkcDFbbl1bbV07Cn0KaW50IExDUzIoc3RyaW5nIHgsc3RyaW5nIHkpIHsKICBpbnQgbiA9IHguc2l6ZSgpOwogIGludCBtID0geS5zaXplKCk7CiAgZm9yKGludCBpPTA7aTw9bjtpKyspIHsKICAgIGZvcihpbnQgaj0wO2o8PW07aisrKSB7CiAgICAgIGlmKGk9PTAgfHwgaj09MCkgewogICAgICAgIGRwMltpXVtqXSA9IDA7CiAgICAgIH0KICAgICAgZWxzZSBpZih4W2ktMV0gPT0geVtqLTFdKSAgewogICAgICAgIGRwMltpXVtqXSA9MStkcDJbaS0xXVtqLTFdOwogICAgICB9CiAgICAgIGVsc2UgewogICAgICAgIGRwMltpXVtqXT0gbWF4KGRwMltpLTFdW2pdLGRwMltpXVtqLTFdKTsKICAgICAgfQogICAgfQogIH0KICByZXR1cm4gZHAyW25dW21dOwp9CmJvb2wgbWFyazFbMjddOwpib29sIG1hcmsyWzI3XTsKaW50IG1haW4oKSB7CiAgaW50IHQ7c2NpKHQpOwogIHdoaWxlKHQtLSkgewogICAgTShtYXJrMSwwKTsKICAgIE0obWFyazIsMCk7CiAgICBzdHJpbmcgYSxiLGMsZDsKICAgIGNpbiA+PiBhID4+IGI7CiAgICBjID0gYTsKICAgIHJldmVyc2UoYy5iZWdpbigpLGMuZW5kKCkpOwogICAgZCA9IGI7CiAgICByZXZlcnNlKGQuYmVnaW4oKSxkLmVuZCgpKTsKICAgIGludCBsZW4xID0gTENTMShhLGMpOwogICAgaW50IGxlbjIgPSBMQ1MyKGIsZCk7CiAgICBpZihsZW4xJTIgJiYgbGVuMiUyKSB7CiAgICAgIGludCB0ZW1wID0gKGxlbjEtMSkvMjsKICAgICAgZm9yKGludCBpPTA7aTxhLnNpemUoKTtpKyspIHsKICAgICAgICBpZihkcDFbaV1bYS5zaXplKCktMS1pXSA9PSB0ZW1wKSB7CiAgICAgICAgICBtYXJrMVthW2ldLSdhJ109dHJ1ZTsKICAgICAgICB9CiAgICAgIH0KICAgICAgaW50IHRlbXAyID0gKGxlbjItMSkvMjsKICAgICAgZm9yKGludCBpPTA7aTxiLnNpemUoKTtpKyspIHsKICAgICAgICBpZihkcDJbaV1bYi5zaXplKCktMS1pXSA9PSB0ZW1wMikgewogICAgICAgICAgbWFyazJbYltpXS0nYSddPXRydWU7CiAgICAgICAgfQogICAgICB9CiAgICAgIGJvb2wgZmxhZyA9IGZhbHNlOwogICAgICBmb3IoaW50IGk9MDtpPDI2O2krKykgewogICAgICAgIGlmKG1hcmsxW2ldICYmIChtYXJrMVtpXSA9PSBtYXJrMltpXSkpIHsKICAgICAgICAgIGZsYWcgPSB0cnVlOwogICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgICB9CiAgICAgIGlmKGZsYWcpIHsKICAgICAgICBjb3V0PDxsZW4xK2xlbjI8PGVuZGw7CiAgICAgIH0KICAgICAgZWxzZSB7CiAgICAgICAgY291dDw8bGVuMStsZW4yLTE8PGVuZGw7CiAgICAgIH0KICAgIH0KICAgIGVsc2UgewogICAgICBjb3V0PDxsZW4xK2xlbjI8PGVuZGw7CiAgICB9CiAgfQp9

Runtime error #stdin #stdout 0.11s 11360KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/C54QLn

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language