求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} LCP(s_i, s_j)\)
方法一
\(1.\)Trie 。
\(2.\)求\(cnt\)，\(cnt[i]\)表示以起点\(0\)到节点\(i\)的简单路径构成的字符串为前缀的字符串数量，可在插入时顺便维护。
\(3.\)求\(get\)，\(get(s_i)\)表示获得\(\sum\limits_{j=1}^{n} LCP(s_i, s_j)\)。
struct trie
{
int t[N][M], idx;
int cnt[N];
void insert(const string &s)
{
int k = 0;
for (auto i : s)
{
int u = i - 'a';
if (!t[k][u]) t[k][u] = ++idx;
k = t[k][u];
cnt[k]++;
}
}
i64 get(const string &s)
{
int k = 0;
i64 res = 0;
for (auto i : s)
{
int u = i - 'a';
if (!t[k][u]) break;
k = t[k][u];
res += cnt[k];
}
return res;
}
};
\(4.\)求\(ans\)，\(ans\)即表示\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} LCP(s_i, s_j)\)。
先往\(t\)中插入所有字符串，再对每个字符串\(get\)求和即可。
Trie t;
for (int i = 1; i <= n; i++) t.insert(a[i]);
i64 ans = 0;
for (int i = 1; i <= n; i++) ans += t.get(a[i]);