定义两个长度相等的字符串\(\{a_i\},\{b_i\}\)的距离为\(\sum_{i=1}^n|a_i-b_{n-i+1}|\)(其中n为字符串的长度)，给出一个字符串\(\{s_i\}\),寻找其中两个长度相等连续的不相交的子串，让两个子串的长度不超过m的情况下，长度的最大值，\(n\leq 5000\)。
解
显然两个串的距离的计算类似回文子串，而两个子串显然会关于一个点对称，由于这个点不一定落在一个字符上，于是我们将字符的所有间隔都加上\('#'\)，然后我们只要在字符上枚举这个中间点，然后把两个子串相对于中间点的外沿向两边尽量扩展，因为距离是随着长度单调递增的，如果发现距离扩展的超过m，就将内沿向外扩展，然后随便记录最大的长度，就可以做到\(O(n^2)\)了。
参考代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define Size 5050
using namespace std;
char s[Size],s1[Size*2];
int main(){
int lsy,m,sl,sl1;scanf("%d",&lsy);
while(lsy--){
sl1=0,scanf("%d%s",&m,s+1),sl=strlen(s+1);
for(int i(1);i<=sl;++i)
s1[++sl1]='#',s1[++sl1]=s[i];
s1[++sl1]='#';int ans(0);
for(int i(1),j,k,sum,tot;i<=sl1;++i){
j=i+1,sum=tot=0;
for(k=i+1;k<=sl1&&2*i-k>0;++k){
sum+=abs(s1[k]-s1[2*i-k]),tot+=s1[k]!='#';
while(sum>m)
sum-=abs(s1[j]-s1[2*i-j]),
tot-=s1[j]!='#',++j;
ans=max(ans,tot);
}
}printf("%d\n",ans);
}return 0;
}