只是给没有思路或者不太理解题意的同学一个更深的认知，也欢迎大家来教我

这么高的复杂度，只能过蓝桥官网的，但我觉得大体思路是可以使用的

思路：将题目所给的环状字符串利用破环成链技巧（相当于复制一遍），求任意两个字符串的最长公共子序列，这正好作为最大生成树的边权

然后求一下最大生成树的权值和即可

这个时间复杂度主要是卡在前半段，求最长公共子串需要“2 * m * m *n * n”的复杂度

（m为未复制时字符串的长度，n为字符串数量）这样会超时，但感觉这个可以优化

虽然我目前还没学qwq

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N =210, M = 40010;

int n,m,res,cnt;
string s[N];
struct E{
    int a,b,w;
    bool operator < (E rhs){
        return this->w<rhs.w;
    }
}edg[M*2];

int p[N];
int find(int x){
    if (p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

//求最大生成树
void kruskal(){
    for(int i=n*(n-1)/2;i>=1;i--){
        int pa=find(edg[i].a);
        int pb=find(edg[i].b);
        if (pa!=pb){
            res+=edg[i].w,p[pa]=pb,cnt++;
        }
    }
}

//求链状求最长公共子串
int cal(string a,string b,int len){
    int f[len+10][len+10];
    int max=0;
    memset(f,0,sizeof f);
    for(int i=1;i<=len;i++){
        for(int j=1;j<=len;j++){
            if (a[i-1]==b[j-1]) f[i][j]= f[i-1][j-1]+1;
            else f[i][j]=0;
            if (f[i][j]>max)   max=f[i][j];
        }
    }
    if (max>len/2)   return len/2;
    else return max;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        p[i]=i;      //初始化并查集
        s[i]+=s[i];  //复制一份贴在后面
    }
    int k =1;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            edg[k++]={i,j,cal(s[i],s[j],2*m)};   //把所有边的权值全部放入
        }
    }
    sort(edg+1,edg+1+n*(n-1)/2);
    kruskal();
    cout<<res<<endl;
    return 0;
}