暴力解法 O ( 26 n 5 ) O(26n^5) O(26n5)
枚举将第 i i i 个字符串的第 j j j 个字符改为 c c c 的所有方案,时间复杂度 O ( 26 n 2 ) O(26n^2) O(26n2),修改并计算总分, O ( n 3 ) O(n^3) O(n3)。
暴力优化 O ( 26 n 3 log n ) O(26n^3\log n) O(26n3logn)
我们可以使用字符串哈希来优化判断两个字符串是否相等。
另外,可以用二分来优化求两个字符串的最大前缀。
枚举所有方案的时间复杂度为 O ( 26 n 2 ) O(26n^2) O(26n2),处理修改以及计算总分的复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
再优化 O ( 26 n 3 ) O(26n^3) O(26n3)
首先,我们依旧使用上述暴力解法中的枚举方式——所有将第 i i i 个字符串的第 j j j 个字符改为 k k k,时间复杂度 O ( 26 n 2 ) O(26n^2) O(26n2)。
接下来我们考虑,如果用不大于 O ( n ) O(n) O(n) 的时间去完成计算一个枚举的分数。
将第 i i i 个字符串的第 j j j 个字符改为 k k k 时,所影响答案的只有 P ( s 1 , s i ) , P ( s 2 , s i ) , P ( s 3 , s i ) , … , P ( s n , s i ) P(s_1, s_i), P(s_2, s_i), P(s_3, s_i), \dots, P(s_n, s_i) P(s1,si),P(s2,si),P(s3,si),…,P(sn,si)。
所以我们可以计算出未修改时的总得分的 t o t tot tot,计算出未修改时第 i i i 个字符串对答案的贡献 g [ i ] g[i] g[i]。设修改之后第 i i i 个字符串对答案的贡献为 r e s res res,那么修改之后的答案即为 t o t − g [ i ] + r e s tot - g[i] + res tot−g[i]+res。
那么接下来,我们要尝试处理计算,将第 i i i 个字符串的第 j j j 个字符改为 k k k 之后,第 i i i 个字符串对答案的贡献。
那么显而易见,我们需要计算修改之后的第 i i i 字符串与剩下 n − 1 n-1 n−1 个字符串的最大前缀。
设其中一个字符串为 s u s_u su,计算修改之后的 s i s_i si 与修改之前,只有第 j j j 个字符被改变, j j j 左侧的字符,以及右侧的字符均为改变。
那么我们可以尝试比较修改前的 s i s_i si 与 s u s_u su 从 0 0 0 开始的最大前缀长度 l e f t left left:
- 若 l e f t < j − 1 left < j - 1 left<j−1,那么 s i s_i si 与 s u s_u su 的最大前缀长度即为 l e f t left left。
- 若 l e f t ≥ j − 1 left \geq j - 1 left≥j−1,那么说明 s i s_i si 与 s u s_u su 的前 j − 1 j - 1 j−1 个字符相等,此时我们需要判断修改之后的第 j j j 个字符是否相等:
- 若第 j j j 个字符相等,则 s i s_i si 与 s u s_u su 的最大前缀即为 l e f t + 1 + left + 1 + left+1+( s i s_i si 与 s j s_j sj 的第 j + 1 j + 1 j+1 个字符开始的最大前缀)。
- 若第 j j j 个字符不相等,则 s i s_i si 与 s u s_u su 的最大前缀即为 l e f t left left。
上述分析中,我们多次需要用到第 i i i 个字符串与第 j j j 个字符串从 k k k 开始的最大前缀。
考虑动态规划: f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 表示第 i i i 个字符串与第 j j j 个字符串从 k k k 开始的最大前缀长度。
考虑动态转移:
- 若 s [ i ] [ k ] = s [ j ] [ k ] s[i][k] = s[j][k] s[i][k]=s[j][k],则 f [ i ] [ j ] [ k ] = f [ i ] [ j ] [ k + 1 ] + 1 f[i][j][k] = f[i][j][k + 1] + 1 f[i][j][k]=f[i][j][k+1]+1。
- 若 s [ i ] [ k ] ≠ s [ j ] [ k ] s[i][k] \neq s[j][k] s[i][k]=s[j][k],则 f [ i ] [ j ] [ k ] = 0 f[i][j][k] = 0 f[i][j][k]=0。
由于计算 f [ i ] [ j ] [ k + 1 ] f[i][j][k + 1] f[i][j][k+1] 时,需要用到 f [ i ] [ j ] [ k + 1 ] f[i][j][k + 1] f[i][j][k+1],故预处理 f f f 数组时需要倒序处理。
暴力优化 O ( 26 n 3 log n ) O(26n^3\log n) O(26n3logn)
#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;elser = 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 ( 26 n 3 ) O(26n^3) O(26n3)
#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;
}
【在线测评】