题目分析

题目要求处理一组字符串，计算最长字符串链的长度。字符串链定义为：每个字符串可以通过在前一个字符串的任意位置添加一个字符得到。例如：

• a → ba（添加 b 到开头）
• ab → acb（添加 c 到中间）
• ab → abc（添加 c 到末尾）

算法思路

1. 字典树（Trie）构建

   • 使用字典树存储所有字符串，便于快速查找前缀匹配。
   • T.ins(ID)：将字符串 s[ID] 插入字典树，记录每个节点的字符串编号 id[pos]。

2. 动态规划（DP）

   • f[i] 表示以字符串 i 结尾的最长链长度。
   • 状态转移：
     • 若字符串 j 是 i 的子序列（少一个字符），则 f[i] = max(f[i], f[j] + 1)。
   • 关键优化：通过字典树快速枚举可能的 j。

3. DFS 搜索（DP 辅助）

   • T.dp(ID, u, len, bo)：在字典树中搜索字符串 s[ID] 的所有可能前驱。
     • bo=1：允许跳过字符（模拟添加操作）。
     • bo=0：严格匹配剩余字符。

DFS 搜索逻辑

• 终止条件：匹配到字符串末尾（len == Len[ID]）。
  • 若当前节点是某个字符串的结尾（id[u]），更新 f[ID]。
• 递归分支：
  • 匹配下一个字符（son[u][c]）。
  • 若允许跳过字符（bo=1），枚举所有可能的字符增减情况。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int maxn=25005;
 
int n=1,ans;
char s[maxn][20];
int f[maxn],Len[maxn];
 
struct Trie {
    int tot;
    int id[maxn*16];
    int son[maxn*16][26];
 
    void ins(int ID) {
        int pos=1,len=strlen(s[ID]+1);
        for(int i=1;i<=len;i++) {
            if(son[pos][s[ID][i]-'a'])
                pos=son[pos][s[ID][i]-'a'];
            else pos=son[pos][s[ID][i]-'a']=++tot;
        }
        id[pos]=ID;
    }
 
    void dp(int ID,int u,int len,int bo) {
        if(len==Len[ID]) {
            if(id[u]&&bo)return;
            if(id[u])f[ID]=max(f[ID],f[id[u]]+1);
            if(bo) {
                for(int i=0;i<26;i++)
                    if(id[son[u][i]])f[ID]=max(f[ID],f[id[son[u][i]]]+1);
            }
            return;
        }
        int c=s[ID][len+1]-'a';
        if(son[u][c])dp(ID,son[u][c],len+1,bo);
        if(bo) {
            for(int i=0;i<26;i++) {
                dp(ID,son[u][i],len,0);
                if(i!=c)dp(ID,son[u][i],len+1,0);
            }
            dp(ID,u,len+1,0);
        }
    }
}T;
 
int main() {
    T.tot=1;
    while(~scanf("%s",s[n]+1))n++;
    for(int i=1;i<n;i++) {
        Len[i]=strlen(s[i]+1),T.dp(i,1,0,1);
        ans=max(ans,f[i]),T.ins(i);
    }
    printf("%d\n",ans+1);
    return 0;
}