Điểm:
1
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Một xâu được gọi là xâu tiền tố của một xâu khác nếu nó xuất hiện ở vị trí đầu tiên của xâu này.
Ví dụ xâu ab
là tiền tố của xâu abcd
; aa
là tiền tố của aa
Yêu cầu: Cho \(n\) xâu ký tự, hãy đếm số cặp xâu mà xâu này là tiền tố của xâu còn lại
Input
- Dòng đầu tiên ghi số nguyên dương \(n\ (1\le n\le 10^6)\)
- \(n\) dòng tiếp theo, mỗi dòng ghi một xâu ký tự chỉ gồm các chữ cái tiếng Anh in thường với độ dài của mỗi xâu không vượt quá \(10\)
Output
- In ra một số nguyên duy nhất là số lượng xâu tìm được.
Example
Test 1
Input
4
abc
aa
aab
aa
Output
3
Bình luận
include <bits/stdc++.h>
using namespace std;
define ll long long
define db double
define pll pair<ll, ll>
define str string
define pii pair<int, int>
define vpii vector<pii>
define vl vector<ll>
define vpll vector<pll>
define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
define mp make_pair
define sz(x) x.size()
define fi first
define pb push_back
define se second
define sqr(i) i * i
define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
define turn_on(i, m) (m |= (1LL << i))
define turn_off(i, m) (m &= ~(1LL << i))
define MASK(i) (1ll << (i))
define BIT(x, i) (((x) >> (i)) & 1)
// x << y : x * (2 ^ y)
// x >> y : x / (2 ^ y)
// (((x) >> i) & 1) : lay ra bit thu i cua x
// (m |= (1LL << i)) : bat bit thu i cua m len
// (m &= ~(1LL << i)) : tat bit thu i cua m
// __builtin_clz(n)) : dem so luong so 0 dung dau
// __builtin_ctz(n)) : dem so luong so 0 dung cuoi
// __builtin_popcount(n) : dem so luong so 1 trong bit
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int MAXN = 2e5 + 1;
const int LOG = 17;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
struct TrieNode {
TrieNode* child[26];
int cnt;
TrieNode() {
for(int i = 0; i < 26; i++)
child[i] = NULL;
cnt = 0;
}
};
TrieNode* root = new TrieNode();
void TrieInsert(const string &s) {
int n = s.size();
TrieNode* p = root;
for(int i = 0; i < n; i++) {
int nxt = s[i] - 'a';
if(p->child[nxt] == NULL)
p->child[nxt] = new TrieNode();
p = p->child[nxt];
p->cnt++;
}
}
bool TrieFind(const string &s) {
int n = s.size();
TrieNode* p = root;
for(int i = 0; i < n; i++) {
int nxt = s[i] - 'a';
if(p->child[nxt] == NULL)
return false;
p = p->child[nxt];
}
return p->cnt>0;
}
void solve(){
ll n;
cin >> n;
vector<string> arr;
for(int i = 0; i < n; i++) {
str s;
cin >> s;
arr.pb(s);
}
sort(arr.begin(), arr.end());
reverse(arr.begin(), arr.end());
ll ans = 0;
map<string, ll> cnt;
for(int i = 0; i < n; i++) {
if(TrieFind(arr[i])) {
TrieNode* p = root;
bool ok = true;
for(int j = 0; j < arr[i].size(); j++) {
int nxt = arr[i][j] - 'a';
if(p->child[nxt] == NULL) {
ok = false;
break;
}
p = p->child[nxt];
}
if(!ok) {
TrieInsert(arr[i]);
continue;
}
ans += p -> cnt;
}
TrieInsert(arr[i]);
}
cout << ans << '\n';
}
int main(){
IOS;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
// #else
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
#endif
solve();
}