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

Download