题目概述

定义字符串 $A$ 和 $B$ 的乘法 $A\times B$ 的结果为将 $B$ 插入 $A$ 的每个空隙中（包含两端），给出 $n$ 个串，求按顺序乘起来之后最长连续相同字符的长度。

解题报告

鬼畜题，LTL秒了。由于 $B$ 会在 $A$ 的每个空隙中插入，所以实际上 $B$ 只需要保留 $B$ 中所有最长连续相同的字符，比如abaab -> aab，这样转化不会影响答案。

那么就很简单了，维护一个数组 $MAX[i]$ 表示当前字符 $i$ 最长连续相同的长度，然后考虑将当前串插入进去产生的贡献，注意一下串由同一个字符构成的情况就行了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000;

int n,len,MAX[26],lst[maxn+5];char s[maxn+5];

#define S(i) (s[i]-'a')
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(scanf("%d",&n),1);i<=n;i++){
        scanf("%s",s+1);int len=strlen(s+1),L=1,R=1;
        for (int i=1;i<=len;i++) lst[i]=(s[i-1]==s[i]?lst[i-1]+1:1);
        for (int i=2;i<=len&&s[i-1]==s[i];i++) L++;for (int i=len;i>=2&&s[i]==s[i-1];i--) R++;
        for (int i=0;i<26;i++) if (L!=len||S(1)!=i) MAX[i]=(MAX[i]?1:0);
        if (L==len) MAX[S(1)]=(MAX[S(1)]+1)*len+MAX[S(1)];
        else MAX[S(1)]=MAX[S(1)]+L,MAX[S(len)]=MAX[S(len)]+R;
        for (int i=1;i<=len;i++) MAX[S(i)]=max(MAX[S(i)],lst[i]);
    }int ans=0;for (int i=0;i<26;i++) ans=max(ans,MAX[i]);printf("%d\n",ans);return 0;
}