回文子串_牛客博客

$子问题：a[i]\sim s[j]和b[k]\sim b[l]组成的串是不是回文串$
$状态方程：f[i][j][k][l],表示a[i]\sim s[j]和b[k]\sim b[l]组成的串是不是回文串$
$j=i+len1-1,l=k+len2-1$
$转移方程：$
$len1+len2<=1时组成的串一定是回文串,此时f[i][j][k][l]=true;$
$len1+len2可以由len1-2+len2左边加a[i]右边加a[j]得出,前提是len1>1$
$此时f[i][j][k][l]|=(f[i+1][j-1][k][l]\&\&a[i]==a[j]);$
$len1+len2同理可由len1+len2-2得出；$
$len1+len2可以由len1-1+len2-1得到$
$可以左边加上a[i]，右边加上b[l]；或者左边加上a[k]右边加上b[j]$
$此时f[i][j][k][l]|=(f[i+1][j][k][l-1]\&\&a[i]==b[l])|(f[i][j-1][k+1][l]\&\&a[j]==b[k]).$
$左边和右边不一定是最外层，只要不改变在原数组中的顺序就可以$
$总结一下，就是长度len=len1+len2的串是不是回文串可以由长度len-2的串推出$
$而长度len-2的串在判断长度len=len1+len2的串时已经判断过了$
$具有相同子结构，可以递推$

$MyCode:$

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7; 
typedef long long ll;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
bool f[101][101][101][101];
char a[101],b[101];
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        int ans=0;
        scanf("%s%s",a+1,b+1);
        int n=strlen(a+1),m=strlen(b+1),j,l;
        for(int len1=0;len1<=n;++len1)
        for(int len2=0;len2<=m;++len2)
        for(int i=1;i+len1-1<=n;++i)
        for(int k=1;k+len2-1<=m;++k) {
            j=i+len1-1,l=k+len2-1;
            if(len1+len2<=1) f[i][j][k][l]=true;
            else{
                f[i][j][k][l]=false;
                if(len1>1) f[i][j][k][l]|=(f[i+1][j-1][k][l]&&a[i]==a[j]);
                if(len1&&len2) f[i][j][k][l]|=(f[i+1][j][k][l-1]&&a[i]==b[l])|(f[i][j-1][k+1][l]&&a[j]==b[k]);
                if(len2>1) f[i][j][k][l]|=(f[i][j][k+1][l-1]&&b[k]==b[l]);
            }
            if(f[i][j][k][l]) ans=max(ans,len1+len2);
        }
        printf("%d\n",ans);
    }
}