分析：
从后往前考虑字符串变成什么样子。
设$S_i = p_1 \cdot p_2 \dots p_{i}$，最后一定是$S_{n - 1} \cdot p_n$，就是将$S_{n-1}$每两个字符之间放入$p_n$。按照$p_n$分类讨论，那么最后有三种情况。
设$p_n$的开头字符是$c0$，结尾字符是$c1$，包含开头的连续段的长度是$len0$，包含结尾的连续段的长度是$len1$。
1、$c0 \neq c1$，那么答案可以是三个：(1).可以是$p_n$中最长的连续子段；(2).如果$S_{n-1}$中存在$c0$，$len0+1$；(3).如果$S_{n-1}$中存在$c1$，$len1+1$。
2、$c0 = c1$，并且整个串不只有一种字符：如果$S_{n-1}$中存在$c0$，那么答案可以是$len0+len1+1$
3、如果$p_n$只有一种字符构成，那么求$S_{n-1}$中最长的字符是$c0$连续段的，设为t，答案是$(t+1) \times len + t$。
可以递归查询。
代码：
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<cctype> #include<set> #include<queue> #include<vector> #include<map> using namespace std; typedef long long LL; inline int read() { int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f; } const int N = 100005; string s[N]; bool a[N][26], b[N]; LL dfs(int x,char c) { if (x == 0) return 0; int ans = a[x - 1][c - ‘a‘], sz = s[x].size(); if (b[x] && s[x][0] == c) { ans = dfs(x - 1, c); return (ans + 1) * sz + ans; } else { int q = 0, h = 0, last = -1; for (int i = 0; i < sz; ++i) { if (s[x][i] == c && last == -1) last = i; if (s[x][i] == c) ans = max(ans, i - last + 1); else last = -1; } for (int i = 0; i < sz; ++i) { if (s[x][i] == c) q ++; else break; } for (int i = sz - 1; ~i; --i) { if (s[x][i] == c) h ++; else break; } if (s[x][0] == c && s[x - 1][sz - 1] == s[x][0] && a[x - 1][c - ‘a‘]) ans = max(ans, q + h + 1); if (s[x][0] == c && a[x - 1][c - ‘a‘]) ans = max(ans, q + 1); if (s[x][sz - 1] == c && a[x - 1][c - ‘a‘]) ans = max(ans, h + 1); if (s[x][0] == c) ans = max(ans, q); if (s[x][sz - 1] == c) ans = max(ans, h); return ans; } } int main() { int n = read(); for (int i = 1; i <= n; ++i) cin >> s[i], b[i] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j < (int)s[i].size(); ++j) if (s[i][j] != s[i][j - 1]) { b[i] = 0; break; } for (int j = 0; j < (int)s[i].size(); ++j) a[i][s[i][j] - ‘a‘] = 1; for (int j = 0; j < 25; ++j) a[i][j] |= a[i - 1][j]; } int ans = 1, q = 1, h = 1, last = 0, sz = s[n].size(); for (int i = 1; i < sz; ++i) { if (last == 0 && s[n][i] == s[n][0]) q ++; if (s[n][i] == s[n][last]) ans = max(ans, i - last + 1); else last = i; } for (int i = sz - 2; i >= 0; --i) { if (s[n][i] == s[n][sz - 1]) h ++; else break; } if (!b[n]) { if (s[n][0] == s[n][sz - 1] && a[n - 1][s[n][0] - ‘a‘]) ans = max(ans, q + h + 1); if (a[n - 1][s[n][0] - ‘a‘]) ans = max(ans, q + 1); if (a[n - 1][s[n][sz - 1] - ‘a‘]) ans = max(ans, h + 1); ans = max(ans, max(q, h)); cout << ans; return 0; } int t = dfs(n - 1, s[n][0]); cout << (t + 1) * sz + t; return 0; }
CF 1131 E. String Multiplication
原文：https://www.cnblogs.com/mjtcn/p/10424484.html