## KHUYÊN CÁC BẠN NÊN SUY NGHĨ TRƯỚC KHI ĐỌC SOLUTION NHAAA
## Ý tưởng
- Khi xây dựng Trie, tại một node $p$ trên Trie, ta có thể lưu số lượng xâu có tiền tố
được thể hiện bởi node $p$
- Vậy khi ta đang thêm một xâu $S$ vào Trie, khi ta đang ở node $p$ và sắp đi xuống $child[p]$
số lượng xâu đã đi xuống $child[p]$ trước đó chính là số xâu có tiền tố khớp với $S$ đến đây.
- => $cnt[p] - cnt[child[p]]$ chính là số lượng xâu có vị trí đầu tiên khác với $S$ tại đây
## Cách giải
- Đầu tiên sort tất cả các xâu theo kích thước giảm dần, điều này giúp tránh những trường hợp ta duyệt qua các xâu ngắn hơn mà là tiền tố của những xâu dài hơn trước. Trường hợp này sẽ khiến chúng ta đếm thiếu.
- Với mỗi xâu ta thêm vào Trie:
- Ta lưu số lượng một node được thăm
- Tăng biến res bằng $(cnt[child[p]] - cnt[p]) * depth$, ([số xâu có vị trí khác với $S$ tại độ sâu này] * [độ dài của tiền tố hiện tại])
## CODE
**[ARE YOU SURE YOU WANT TO PROCEED]**
```cpp
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define upb upper_bound
#define lwb lower_bound
#define FILE(task) freopen(task".inp","r",stdin);freopen(task".out","w",stdout);
#define int ll
typedef long long ll;
typedef long double lldb;
///--------------------------------------------------------------------------------///
//VARIABLES
const int MAXN = 2e6 + 5;
int n;
string s[100009];
int trie[MAXN][26];
int cnt[MAXN];
int nodes = 1;
//FUNCTIONS
bool cmp(const string &x, const string &y)
{
return x.size() > y.size();
}
int addString(string x)
{
int cc = 0;
int depth = 1;
int p = 0;
cnt[p]++;
for (char c : x)
{
int cur = c - 'a';
if (!trie[p][cur]) trie[p][cur] = nodes++;
int child = trie[p][cur];
cnt[child]++;
cc += (cnt[p] - cnt[child]) * depth;
p = child;
depth++;
}
return cc;
}
//PROCESS
void read()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
}
}
void solve()
{
int res = 0;
sort(s + 1, s + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
res += addString(s[i]);
}
cout << res;
}
//MAIN
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//FILE("test");
read();
solve();
return 0;
}
```
kevinPhan
Created at
0 likes