今学习Trie树:https://blog.csdn.net/weixin_43792276/article/details/98977397
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include<iostream> #include<algorithm> #include<string> using namespace std; const int MaxN = 5000; int trie[MaxN][26]; int cnts[MaxN]; int tot; void trieInsert(string s) { int node = 0; for (int i = 0; i < s.size(); i++) { if (!trie[node][s[i] - 'a'])node = trie[node][s[i] - 'a'] = ++tot; else node = trie[node][s[i] - 'a']; } cnts[node]++; } void trieAccumulate(int node) { for (int i = 0; i < 26; i++) { if (trie[node][i]) { cnts[trie[node][i]] += cnts[node]; trieAccumulate(trie[node][i]); } } } int main() { int n; string s; cin >> n; while (n--) { cin >> s; trieInsert(s); } trieAccumulate(0); int result = 0; for (int i = 0; i <= tot; i++)result = max(result, cnts[i]); cout << result; } |