题解 | #合并回文子串#

package main

import (
	"bufio"
	"fmt"
    "os"
)

var in = bufio.NewReader(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
// a[i] == a[j]
// dp[i-1][j-1][k][l] > 0 dp[i][j][k][l] |= dp[i-1][j-1][k][l
// a[i] == b[l]
// dp[i-1][j][k][l-1] > 0 dp[i][j][k][l] |= dp[i-1][j][k][l-1]
// b[k] == a[j]
// dp[i][j-1][k+1][l] > 0 dp[i][j][k][l]] |= dp[i][j-1][k+1][l]
// b[k] == b[l]
// dp[i][j][k+1][l-1] > 0 dp[i][j][k][l] |= dp[i][j][k+1][l-1] 
func do() {
    var a, b string
    var dp [52][52][52][52]int
    var ans int
 
    fmt.Fscan(in, &a)
     fmt.Fscan(in, &b)
    lena := len(a)
    lenb := len(b)
    a = " "+a 
    b = " "+b
    ans = 1
    for la := 0; la <= lena; la++{
        for lb :=0 ; lb <= lenb; lb++{
            for i := 1;  i+la -1 <= lena; i++ {
                for k := 1;  k+lb-1 <= lenb; k++{
                    j := i + la -1
                    l := k +lb -1
                    if la + lb <=1 {
                        dp[i][j][k][l] = 1
                    } else  {
                        if i<= lena {
                            if i<= lena && a[i] == a[j] && j >0{
                                dp[i][j][k][l] |= dp[i+1][j-1][k][l] 
                            }
                            if i<= lena && a[i] == b[l] && l >0 {
                                dp[i][j][k][l] |= dp[i+1][j][k][l-1]
                            }
                        }
                        if k <= lenb {
                            if  b[k] == a[j] && j > 0{
                                dp[i][j][k][l] |= dp[i][j-1][k+1][l]
                            }
                            if   b[k] == b[l] && l > 0{
                                dp[i][j][k][l] |=  dp[i][j][k+1][l-1]
                            }
                        }
                        if dp[i][j][k][l] > 0 && la+lb > ans {
                            ans = la+lb
                        }
                    }
                }
            }
        }
    }
    fmt.Fprintln(out, ans)
}
func main() {
    defer out.Flush()
   var t int
   fmt.Fscan(in, &t)
   for i := 0; i < t; i++ {
    do()
   }
}