CHAIN2 - Chuỗi từ
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
using namespace std;
const int L = 250000 + 5;
int trie[L][26], nnode, f[L], finish[L];
char s[L];
void mark(const char * s) {
int u = 0;
for(int i = 0; s[i]; ++i) {
int t = s[i] - 'a';
if(trie[u][t] == 0)
trie[u][t] = ++nnode;
u = trie[u][t];
}
finish[u] = 1;
}
void solve() {
for(int i = nnode; i >= 0; --i) {
for(int j = 0; j < 26; ++j)
if(trie[i][j]) f[i] = max(f[i], f[trie[i][j]]);
f[i] += finish[i];
}
printf("%d\n", f[0]);
}
int main() {
int m; scanf("%d", &m);
while(m--) {
scanf("%s", s);
mark(s);
}
solve();
return 0;
}