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

Download