吊坠 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 200 + 100;
const int maxm = 100 + 100;
struct Edge {
    int u, v, w;
};

bool operator<(const Edge &a, const Edge &b) {
    return a.w > b.w;
}

int n, m, mm, ecnt, ans;
char str[maxn][maxm];
Edge edge[maxn * maxn];
int fa[maxn];
int dp[maxm][maxm];

void init() {
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
    }
}

int findF(int x) {
    return x == fa[x] ? x : fa[x] = findF(fa[x]);
}

void union_(int x, int y) {
    fa[findF(x)] = findF(y);
}

int dis(char *s1, char *s2) {
    int ret = 0;
    for (int i = 1; i <= mm; ++i) {
        for (int j = 1; j <= mm; ++j) {
            if (s1[i] == s2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = 0;
            }
            ret = max(ret, dp[i][j]);
        }
    }
    return min(ret, m);
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    scanf("%d%d", &n, &m);
    mm = m << 1;
    init();
    for (int i = 0; i < n; ++i) {
        scanf("%s", str[i] + 1);
        memcpy(str[i] + 1 + m, str[i] + 1, sizeof(char) * m);
        for (int j = 0; j < i; ++j) {
            edge[ecnt++] = {i, j, dis(str[i], str[j])};
        }
    }
    sort(edge, edge + ecnt);
    for (int i = 0; i < ecnt; ++i) {
        int u = edge[i].u;
        int v = edge[i].v;
        if (findF(u) != findF(v)) {
            union_(u, v);
            ans += edge[i].w;
        }
    }
    cout << ans << endl;

    return 0;
}