CHAIN2 - Chuỗi từ
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int N = 250002;
using namespace std;
int n; char s[N];
class Trie {
public:
struct node {
int a[26]; int e;
int& operator[] (int i) {return a[i];}
node() {for(int i = 0; i<26; i++) a[i] = 0; e = 0;}
};
int ans;
vector<node> a;
void Add(char *s) {
int pos = 0, i, c;
for(i = 0; c = s[i]; i++) {
if (a[pos][c - 'a'] == 0) {
a.push_back(node());
a[pos][c - 'a'] = a.size() - 1;
}
pos = a[pos][c - 'a'];
}
a[pos].e = 1;
}
void clear() {a.clear(); a.push_back(node());}
void DFS(int u, int cnt) {
if (a[u].e == 1) {
cnt++; ans = max(ans, cnt);
}
for(int i=0; i<26; i++)
if (a[u][i] != 0)
DFS(a[u][i], cnt);
}
int Find() {
ans = 0;
DFS(0, 0);
return ans;
}
Trie() {clear();};
};
Trie T;
int main()
{
scanf("%d\n", &n);
for(int i=1; i<=n; i++) {
gets(s);
T.Add(s);
}
int res = T.Find();
printf("%d", res);
return 0;
}