自动搬运

查看原文

来自洛谷，原作者为

	FJ_EYoungOneC 这个人很勤快，但是他并不想留下什么

搬运于2025-08-24 23:12:55，当前版本为作者最后更新于2025-04-13 08:46:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下文中记 $C = 26$，表示字符种类的数量。

暴力解法 $O(Cn^5)$

枚举将第 $i$ 个字符串的第 $j$ 个字符改为 $c$ 的所有方案，时间复杂度 $O(Cn^2)$，修改并计算总分，$O(n^3)$。

暴力优化 $O(Cn^3\log n)$

我们可以使用字符串哈希来优化判断两个字符串是否相等。

另外，可以用二分来优化求两个字符串的最大前缀。

枚举所有方案的时间复杂度为 $O(Cn^2)$，处理修改以及计算总分的复杂度为 $O(n\log n)$。

再优化 $O(Cn^3)$

首先，我们依旧使用上述暴力解法中的枚举方式——所有将第 $i$ 个字符串的第 $j$ 个字符改为 $k$，时间复杂度 $O(Cn^2)$。

接下来我们考虑，如果用不大于 $O(n)$ 的时间去完成计算一个枚举的分数。

将第 $i$ 个字符串的第 $j$ 个字符改为 $k$ 时，所影响答案的只有 $P(s_1, s_i), P(s_2, s_i), P(s_3, s_i), \dots, P(s_n, s_i)$。

所以我们可以计算出未修改时的总得分的 $tot$，计算出未修改时第 $i$ 个字符串对答案的贡献 $g[i]$。设修改之后第 $i$ 个字符串对答案的贡献为 $res$，那么修改之后的答案即为 $tot - g[i] + res$。

那么接下来，我们要尝试处理计算，将第 $i$ 个字符串的第 $j$ 个字符改为 $k$ 之后，第 $i$ 个字符串对答案的贡献。

那么显而易见，我们需要计算修改之后的第 $i$ 字符串与剩下 $n-1$ 个字符串的最大前缀。

设其中一个字符串为 $s_u$，计算修改之后的 $s_i$ 与修改之前，只有第 $j$ 个字符被改变，$j$ 左侧的字符，以及右侧的字符均为改变。

那么我们可以尝试比较修改前的 $s_i$ 与 $s_u$ 从 $0$ 开始的最大前缀长度 $left$：

• 若 $left < j - 1$，那么 $s_i$ 与 $s_u$ 的最大前缀长度即为 $left$。
• 若 $left \geq j - 1$，那么说明 $s_i$ 与 $s_u$ 的前 $j - 1$ 个字符相等，此时我们需要判断修改之后的第 $j$ 个字符是否相等：
  • 若第 $j$ 个字符相等，则 $s_i$ 与 $s_u$ 的最大前缀即为 $left + 1 +$（$s_i$ 与 $s_j$ 的第 $j + 1$ 个字符开始的最大前缀）。
  • 若第 $j$ 个字符不相等，则 $s_i$ 与 $s_u$ 的最大前缀即为 $left$。

上述分析中，我们多次需要用到第 $i$ 个字符串与第 $j$ 个字符串从 $k$ 开始的最大前缀。

考虑动态规划：$f[i][j][k]$ 表示第 $i$ 个字符串与第 $j$ 个字符串从 $k$ 开始的最大前缀长度。

考虑动态转移：

• 若 $s[i][k] = s[j][k]$，则 $f[i][j][k] = f[i][j][k + 1] + 1$。
• 若 $s[i][k] \neq s[j][k]$，则 $f[i][j][k] = 0$。

由于计算 $f[i][j][k]$ 时，需要用到 $f[i][j][k + 1]$，故预处理 $f$ 数组时需要倒序处理。

暴力优化 $O(Cn^3\log n)$

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

using namespace std;

const int N = 2e2 + 10, P = 131;

typedef unsigned long long ULL;

int n;
string str[N];
ULL f[N][N], p[N];
int g[N];
int tot;

ULL query(int u, int l, int r)
{
    return f[u][r] - f[u][l - 1] * p[r - l + 1];
}

int calc(int u, bool flag)
{
    int res = 0;
    for (int i = 1; i <= n; ++ i )
        if (i != u)
        {
            int l = 1, r = min(str[u].size() - 1, str[i].size() - 1);
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (query(i, 1, mid) == query(u, 1, mid))
                    l = mid;
                else
                    r = mid - 1;
            }
            if (query(i, 1, l) == query(u, 1, l))
                res += l;
        }
    
    if (flag)
    {
        g[u] = res;
        tot += res;
    }
    
    return res;
}

int modify(int u, int k, int c)
{
    char t = str[u][k];
    str[u][k] = 'a' + c;
    
    for (int i = 1; i < str[u].size(); ++ i )
        f[u][i] = f[u][i - 1] * P + str[u][i];

    int res = tot - g[u] * 2 + calc(u, false) * 2;
    
    str[u][k] = t;
    
    for (int i = 1; i < str[u].size(); ++ i )
        f[u][i] = f[u][i - 1] * P + str[u][i];
    
    return res / 2;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n; ++ i )
    {
        cin >> str[i];
        str[i] = ' ' + str[i];
    }
    
    p[0] = 1;
    for (int i = 1; i < N; ++ i )
        p[i] = p[i - 1] * P;
    
    for (int i = 1; i <= n; ++ i )
        for (int j = 1; j < str[i].size(); ++ j )
            f[i][j] = f[i][j - 1] * P + str[i][j];
    
    for (int i = 1; i <= n; ++ i )
        calc(i, true);
    
    int res = 0;
    for (int i = 1; i <= n; ++ i )
        for (int j = 1; j < str[i].size(); ++ j )
            for (int k = 0; k < 26; ++ k )
                res = max(res, modify(i, j, k));
    
    cout << res << endl;
    
    return 0;
}

再优化 $O(Cn^3)$

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

using namespace std;

const int N = 2e2 + 10;

int n;
string str[N];
int g[N];
int tot;
int f[N][N][N];     //  [i, j, k] 第i个字符串和 第j个字符串 k个字符起最大连续数量

void init()
{
    for (int i = 1; i <= n; ++ i )
        for (int j = i + 1; j <= n; ++ j )
        {
            int mn = min(str[i].size(), str[j].size());
            for (int k = mn - 1; k >= 0; -- k )
                if (str[i][k] == str[j][k])
                    f[i][j][k] = f[j][i][k] = f[i][j][k + 1] + 1;
        }
    
    for (int i = 1; i <= n; ++ i )
    {
        for (int j = 1; j <= n; ++ j )
            g[i] += f[i][j][0];
        tot += g[i];
    }
    
    tot /= 2;
}

int modify(int u, int k, int c)
{
    int res = 0;
    for (int i = 1; i <= n; ++ i )
        if (i != u)
        {
            int left = min(f[u][i][0], k);
            res += left;
            
            if (left == k && str[i].size() > k && str[i][k] - 'a' == c)
            {
                res ++;
                res += f[u][i][k + 1];
            }
        }
    
    return tot - g[u] + res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n; ++ i )
        cin >> str[i];
    
    init();
    
    int res = 0;
    for (int i = 1; i <= n; ++ i )
        for (int j = 0; j < str[i].size(); ++ j )
            for (int k = 0; k < 26; ++ k )
                res = max(res, modify(i, j, k));
    
    cout << res << endl;
    
    return 0;
}