CHAIN2 - Chuỗi từ
Tác giả: hieult
Ngôn ngữ: C++
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <deque>
#include <iostream>
#include <iomanip>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <string> vs;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, a) for (int i = 0; i < (a); i++)
#define REPD(i, a) for (int i = ((a) - 1); i >= 0; i--)
#define FIT(it, v) for (typeof((v).begin())it = (v).begin(); it != (v).end(); ++it)
#define FITD(it, v) for (typeof((v).rbegin())it = (v).rbegin(); it != (v).rend(); ++it)
#define fe(i,a) for(__typeof(a.begin()) i=a.begin();i!=a.end();i++)
#define VAR(a, b) typeof(b) a(b)
#define ALL(v) (v).begin(), (v).end()
#define SET(a, x) memset((a), (x), sizeof(a))
#define SIZE(a) ((int)(a).size())
#define EXIST(a, b) (find(ALL(a), (b)) != (a).end())
#define SORT(x) sort(ALL(x))
#define GSORT(x) sort(ALL(x), greater<typeof(*((x).begin()))>())
#define UNIQUE(v) SORT(v); (v).resize(unique(ALL(v)) - (v).begin())
#define ENUM(v) FIT(it, (v)) cout << *it << " "; cout << endl
#define PF push_front
#define PB push_back
#define MP make_pair
#define F first
#define S second
// bit operater
int BIT(ll x,int i) { return(x&(1<<i));}
ll ONBIT(int i,ll x){ return(x|(1<<i));}
ll OFFBIT(int i,ll x){return (x& ~(1<<i));}
ll FLIPBIT(int i,ll x){return (x^(1<<i));}
const char IN[] = "_.in";
const char OUT[] = "_.out";
const int maxn=255555;
struct vertex
{
int next[26];
};
vertex Trie[maxn];
int fx[maxn]; // so leaf da chay qua
int n,now,sz,res=0;
string s[maxn];
void init()
{
SET(fx,0);
SET(Trie[0].next,-1);
sz=1;
}
void add(string a)
{
int now=0;
FOR(i,0,a.length()-1)
{
int c=a[i]-'a';
if (Trie[now].next[c]==-1)
{
SET(Trie[sz].next,-1);
fx[sz]=fx[now];
Trie[now].next[c]=sz;
sz++;
}
res=max(res,fx[now]);
now=Trie[now].next[c];
}
fx[now]++;
res=max(res,fx[now]);
}
int main() {
//freopen(IN, "r", stdin);
// freopen(OUT, "w", stdout);
cin>>n;
FOR(i,1,n) cin>>s[i];
sort(s+1,s+n+1);
init();
FOR(i,1,n) add(s[i]);
cout<<res;
}