\(对每个s_i的前缀s_{i, 1…j}进行与所有后缀比较，相同的次数记为res_{i,j}，此处可以用哈希进行比较 \)
\(因为要取最大前缀，所以要用kmp求出next数组后res_{i,next[j]} -= res_{i, j}，注意一下下标的偏移 \)
\(答案就是\Sigma_{i=1}^n\Sigma_{j=1}^{len_i}j^2res_{i,j} \)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <string> #include <iostream> #include <string.h> #include <unordered_map> #define MOD 998244353 #define MAXN 100010 #define MAXS 1000010 #define LL long long using namespace std; int n, nt[MAXS]; LL ans, res[MAXS]; string s[MAXN]; unordered_map<unsigned long long, LL> cnt; int main() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> s[i]; unsigned long long x = 0, p = 1; for (int j = s[i].size() - 1; j >= 0; --j) { x += (s[i][j] - 'a' + 1) * p; cnt[x]++; p *= 233; } } for (int i = 1; i <= n; ++i) { unsigned long long x = 0, p = 1; for (int j = 0; j < s[i].size(); ++j) { x = x * 233 + s[i][j] - 'a' + 1; res[j + 1] = cnt[x]; p *= 233; } for (int j = 1; j < s[i].size(); ++j) { int k = nt[j - 1]; while (k && s[i][k] != s[i][j]) k = nt[k - 1]; if (s[i][k] == s[i][j]) k++; nt[j] = k; } for (int j = 1; j <= s[i].size(); ++j) { res[nt[j-1]] -= res[j]; } for (int j = 1; j <= s[i].size(); ++j) { ans = (ans + (((1LL * res[j] * j) % MOD) * j) % MOD) % MOD; } } printf("%lld\n", ans); return 0; } |