题目链接:http://codeforces.com/contest/1131/problem/E
题目大意
给定一个字符串的运算规则，
给定若干个字符串，问运算到最后其最长的连续相同串是
多长。
题目分析
首先考虑最后一个串，
这题情况稍微有点多，但是理清楚就简单了，
首先我们可以维护一个数组is_have[maxn][26]
表示前i个串中出现过哪些字符，
因为最后一个串是附加到前一个结果串的每一个字符之间。
所以可以这样分析：
考虑是否只有一个字符：如果只有一个，那么情况可以递归，
定义dfs（n,c）表示前n个字符串组成的结果串中c的连续长度是多少，
不难整理出最终答案。
如果不止一个，那么我们预处理出前后缀相同串最大长度，
在判定之前不妨先把串中连续相同子串的最大长度搞出来，
判定前后缀字符是否一样：这时候有三种情况可以对答案产生更新：
一种是前缀后缀字符一样并且字符在前n-1个字符串中出现过，
一种是前缀字符在前n-1个字符串中出现过，
最后一种就是后缀字符在前n-1个字符串中出现过，
对于dfs里面的情况，其实和上面讨论差不多，只不过是要针对字符c而言，
有些细节判定清楚即可。
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=1e5+5;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
给定一个字符串的运算规则，
给定若干个字符串，问运算到最后其最长的连续相同串是
多长。题目分析：
首先考虑最后一个串，
这题情况稍微有点多，但是理清楚就简单了，
首先我们可以维护一个数组is_have[maxn][26]
表示前i个串中出现过哪些字符，
因为最后一个串是附加到前一个结果串的每一个字符之间。
所以可以这样分析：
考虑是否只有一个字符：如果只有一个，那么情况可以递归，
定义dfs（n,c）表示前n个字符串组成的结果串中c的连续长度是多少，
不难整理出最终答案。
如果不止一个，那么我们预处理出前后缀相同串最大长度，
在判定之前不妨先把串中连续相同子串的最大长度搞出来，
判定前后缀字符是否一样：这时候有三种情况可以对答案产生更新：
一种是前缀后缀字符一样并且字符在前n-1个字符串中出现过，
一种是前缀字符在前n-1个字符串中出现过，
最后一种就是后缀字符在前n-1个字符串中出现过，
对于dfs里面的情况，其实和上面讨论差不多，只不过是要针对字符c而言，
有些细节判定清楚即可。*/
ll ans=0,cnt=0;
string s[maxn];
bool is_have[maxn][26];
ll dfs(int n,char c){if(!n) return 0;if(is_have[n][c-'a']==false) return 0;int len=s[n].size(),flag=0;ll cnt=0,ans=is_have[n][c-'a']?1:0;rep(i,0,len){cnt=1;while(i+1<len&&s[n][i]==s[n][i+1]&&s[n][i]==c)cnt++,i++;if(s[n][i]==c) ans=max(ans,cnt);}rep(i,0,len) if(i+1<len&&s[n][i]!=s[n][i+1]) {flag=1;break;}if(flag){///if it has at least two colorsll l=0,r=len-1;while(l<len&&s[n][l]==c) l++;while(r>=0&&s[n][r]==c) r--;///cout<<l<<" "<<len-r<<endl;if(is_have[n-1][c-'a']&&s[n][len-1]==s[n][0]&&s[n][0]==c)ans=max(ans,l+len-r);if(is_have[n-1][s[n][0]]) ans=max(ans,l+1);if(is_have[n-1][s[n][len-1]]) ans=max(ans,len-r);}else if(s[n][0]==c){ll ret=dfs(n-1,c);ans=max(ans,1LL*(1+ret)*s[n].size()+ret);}return ans;
}
int n;
int main(){mst(is_have,false);cin>>n;rep(i,1,n+1){cin>>s[i];rep(j,0,26) if(is_have[i-1][j])is_have[i][j]=true;rep(j,0,s[i].size())is_have[i][s[i][j]-'a']=true;}///把每个位置上每个字符的前缀包含情况考虑进去int flag=0,len=s[n].size();rep(i,0,len-1) if(s[n][i]!=s[n][i+1]) {flag=1;break;}if(flag){for(int i=0;i<len;i++){cnt=1;while(i+1<len&&s[n][i]==s[n][i+1])cnt++,i++;ans=max(ans,cnt);}///把一些情况容纳进去int l=0,r=len-1;while(s[n][l]==s[n][l+1]) l++;while(s[n][r]==s[n][r-1]) r--;if(s[n][0]==s[n][len-1]&&is_have[n-1][ s[n][len-1]-'a' ]){ans=max(ans,1LL*(len-r+l+2));}if(is_have[n-1][s[n][0]-'a']) ans=max(ans,1LL*l+2);///左边if(is_have[n-1][s[n][len-1]-'a']) ans=max(ans,1LL*len-r+1);///右边}else{ll ret=dfs(n-1,s[n][0]);ans=max(ans,1LL*(1+ret)*s[n].size()+ret);}cout<<ans<<endl;return 0;
}