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;
}

Download