大家好，我喜欢 Hash，所以我用 Hash 通过了这道题。
思路：
处理方法有点类似于P6521
首先我们最终接出的字符串要求其中的小字符串按字典序排序，那么我们就将所有字符串排好序后从前往后枚举（其实题目已经给我们排好序了，但有些人可能没有注意到），每次枚举到一个字符串就更新把它作为答案串结尾的最大长度。
然后注意到一一枚举从 a 到 z 的每一个字母会让复杂度爆掉，那么我们就用一个空字符（比如 #）来代替要变换的部分。
举个例子，对于字符串 adcb，它可以由 adb 加一个字符 c 变换过来，那么我们就会在枚举到 adb 时将状态 ad#b 压入到 Hash 中，之后枚举到 adcb 时就可以用 ad#b 来更新答案。
具体过程：
令当前枚举到第 \(i\) 个字符串，我们先更新这个字符串作为结尾的答案。
分三种变换（两种情况）：
- 添加 & 修改一个字母
枚举每一位字符，将其变为#后把在 Hash 中查找该串，更新找到的最大长度。 - 删除一个字母（当前字符串长度不能为16）
枚举每一个字符间的位置，把#插进去后在 Hash 中查找，更新找到的最大长度。
将找到的最大长度 +1 后更新到最终答案里。
然后再插入这个字符串，也分三种变换两种情况，但删除和添加操作调换了一下：
- 删除 & 修改一个字母
枚举每一位字符，将其变为#后把它塞进 Hash。 - 添加一个字母（当前字符串长度不能为16）
枚举每一个字符间的位置，把#插进去后把串塞进 Hash。
最后我们会发现这样会让相同的字符串重复统计，那么我们在一开始就把相同的字符串去掉就好，不影响最终结果。
更具体一点看代码（写的有点 Naive）：
code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll Max(ll x, ll y){return x > y ? x : y;}
inline ll rd(){
ll x = 0;bool f = true;char c = getchar();
while (c < '0' || c > '9'){if (c == '-') f = false; c = getchar();}
while (c >= '0' && c <= '9'){x = (x<<3) + (x<<1) + (c ^ 48);c = getchar();}
return f ? x : -x;
}
const int N = 2.5e4 + 10, M = 1e5 + 7;
class Hash_table{
private:
struct Node{
int nextt, num;// num 是 “str” 这个状态的最大长度
string str;
}data[N * 50];int head[M + 10], cnt;
int h(string s){
int l = s.size(), res = 0;
for(int i = 0; i < l; ++i)
res = ((res << 4) + int(s[i] - 'a') + M) % M;
return res;
}
public:
int find(string s){
int key = h(s);
for(int i = head[key]; i; i = data[i].nextt)
if(s == data[i].str)
return data[i].num;
return 0;
}
void insert(string s, int val){
int key = h(s);
for(int i = head[key]; i; i = data[i].nextt){
if(s == data[i].str){
data[i].num = Max(data[i].num, val);
return ;
}
}
data[++cnt].nextt = head[key];
data[cnt].num = val;
data[cnt].str = s;
head[key] = cnt;
return ;
}
}H;
int n;
int ans;
string s, lst = "", tmp, tmp1, tmp2;// lst用来去重，一坨tmp用来枚举带’#’的字符串
int main(){
n = rd();
for(int i = 1; i <= n; ++i){
cin >> s;
if(s == lst)continue;
lst = s;
int l = s.size(), val = 0;// val是以当前串结尾的串的最大长度
tmp = s;
for(int j = 0; j < l; ++j){// 查找之前 添加和修改 的字符串
tmp[j] = '#';
val = Max(val, H.find(tmp));
tmp[j] = s[j];
}
if(l < 16)// 查找之前 删除 的字符串
for(int j = 0; j <= l; ++j){
tmp = "", tmp1 = "", tmp2 = "";
for(int k = 1; k <= j; ++k)// 用一堆 += 时间更优
tmp1 += s[k - 1];
for(int k = j + 1; k <= l; ++k)
tmp2 += s[k - 1];
tmp += tmp1;
tmp += '#';
tmp += tmp2;
val = Max(val, H.find(tmp));
}
val++;
ans = Max(ans, val);// 更新最终答案
tmp = s;
for(int j = 0; j < l; ++j){// 插入 删除和修改 后的字符串
tmp[j] = '#';
H.insert(tmp, val);
tmp[j] = s[j];
}
if(l < 16)// 插入 添加 后的字符串
ans = Max(ans, val);
for(int j = 0; j <= l; ++j){
tmp = "", tmp1 = "", tmp2 = "";
for(int k = 1; k <= j; ++k)
tmp1 += s[k - 1];
for(int k = j + 1; k <= l; ++k)
tmp2 += s[k - 1];
tmp += tmp1;
tmp += '#';
tmp += tmp2;
H.insert(tmp, val);
}
}
printf("%d", ans);
return 0;
}