题面
英文题面
题意：定义两个字符串(s)和(t)（(s)的长度为(m)）的乘积为: (t+s_1+t+s_2+dots+t+s_m+t) 。
定义一个字符串的美丽度为最长的相同字母连续子序列的长度。现在给出(n)个字符串(p_i) ，问
(((p_1p_2)p_3)dots p_n)的美丽度。
(|s|,|t|,n,sum p_i leq 10^5)
题解：
对每个字母分别考虑。设最后一个串为(S)。
发现答案只可能是(S)的一个子串，或是(S)的一段前缀和后缀，或是若干个完整的(S)拼接起来。
对于第一种情况，直接扫一遍就行了。
对于后两种情况，由于前(n-1)个串最后都得分开，它们只能作为连接两个或若干个(S)的连接字符。
那么对于第二种情况，显然贡献就是(S)的一段后缀+1+(S)的一段前缀。
对于第三种情况，也就是当前串所有字符都为指定的字符时，我们需要维护之前的操作得到的串的最长连续字符个数。
设之前的最长连续字符数为(sum)，当前(t)串的长度为(len)，那么操作后得到的最长连续字符个数即为：(len*(sum+1)+sum)。
时间复杂度：(O(sum p_i))
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
char s[101000];
vector<int>c[101000];
int n,m,ans,len[101000],pre[101000],suf[101000],mx[101000],cnt;
I solve(int x){
F(i,1,n){
pre[i]=0;
while(pre[i]<len[i]&&c[i][pre[i]+1]==x)pre[i]++;
suf[i]=0;
while(suf[i]<len[i]&&c[i][len[i]-suf[i]]==x)suf[i]++;
mx[i]=cnt=0;
F(j,1,len[i]){
if(c[i][j]==x)cnt++;
else cnt=0;
mx[i]=max(mx[i],cnt);
}
// cout<<pre[i]<<" "<<suf[i]<<" "<<mx[i]<<endl;
// ans=max(ans,mx[i]);
}
ans=max(ans,mx[n]);
re num=mx[1];
F(i,2,n){
if(pre[i]==len[i]){
if(num)num+=(len[i]*(num+1));
else num=len[i];
}
else num?num=pre[i]+suf[i]+1:num=max(pre[i],suf[i]);
num=max(num,mx[i]);
// cout<<num<<endl;
}
ans=max(ans,num);
// cout<<endl;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
F(i,1,n){
cin>>s+1;len[i]=strlen(s+1);c[i].resize(len[i]+1);
F(j,1,len[i])c[i][j]=s[j]-'a'+1;
}
F(t,1,26)solve(t);
cout<<ans;
return 0;
}