题解 | 合并回文子串

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  我是看了题解写的，一开始没有看范围感觉自己写不了就直接看题解了，不过这个思路我应该也确实不会想到，不过其实我还是没有完全理解代码思路，我不太明白为什么不用考虑s[ls] == ss[lss] 的情况以及 ss[rs] == ss[lss] 的情况,等等我现在去试试会不会出错————ok,我回来了，出错了输出>=预期答案,如果有知道的话请您评论回(●'◡'●)
#include <iostream>
#include <string>
#include <bitset>
using namespace std;
bool dp[55][55][55][55];
int main() {
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  int T;
  cin >> T;
  while(T--){
    int ans = 1;
    string s, ss;
    cin >> s >> ss;
    size_t size = s.size(), ssize = ss.size();
    s = ' ' + s; ss = ' ' + ss;
    for(int lens = 0; lens <= size; lens++){
      for (int lenss = 0; lenss <= ssize; lenss++){
        for (int ls = 1; ls + lens - 1 <= size; ls++){
          for (int lss = 1; lss + lenss -1 <= ssize; lss++){
            int rs = ls + lens - 1, rss = lss + lenss - 1;
            if (lens + lenss <= 1) dp[ls][rs][lss][rss] = 1;
            else {dp[ls][rs][lss][rss] = 0;
            if (s[ls] == s[rs]) dp[ls][rs][lss][rss] |= dp[ls + 1][rs - 1][lss][rss];
            if (s[ls] == ss[rss]) dp[ls][rs][lss][rss] |= dp[ls + 1][rs][lss][rss - 1];
            if (ss[lss] == s[rs]) dp[ls][rs][lss][rss] |= dp[ls][rs - 1][lss + 1][rss];
            if (ss[lss] == ss[rss]) dp[ls][rs][lss][rss] |= dp[ls][rs][lss + 1][rss - 1];
            if (dp[ls][rs][lss][rss]) ans = max(ans, lens + lenss);
            }
          }
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
// 64 位输出请用 printf("%lld")