CHAIN2 - Chuỗi từ
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define Rep(i,n) for(int i=0,lll=(n);i<lll;++i)
#define For(i,a,b) for(int i=(a),lll=(b);i<=lll;++i)
#define Ford(i,a,b) for(int i=(a),lll=(b);i>=lll;--i)
#define pb push_back
#define MP make_pair
#define fi first
#define se second
#define nextint __nextint()
inline int __nextint() { int x; scanf("%d", &x); return x; }
const int MAXN = 250050;
char buf[MAXN];
char *a[MAXN];
int n;
int L[MAXN], F[MAXN];
bool cmp(char * a, char * b) {
return strcmp(a,b) < 0;
}
bool check(char *a, char *b) {
for(int i=0;a[i]!=0 && b[i]!=0;++i) {
if(a[i]!=b[i]) return false;
}
return true;
}
int main() {
scanf("%d", &n);
gets(buf);
Rep(i,n) {
gets(buf);
int ls = strlen(buf);
a[i] = new char[ls + 1];
memmove( a[i], buf, ls + 1);
}
sort( a, a + n, cmp);
// Rep(i,n) printf("%s\n", a[i]);
Rep(i,n) {
int j = i - 1;
while(j >= 0 && !check(a[j], a[i])) j = L[j];
L[i] = j;
}
int best = 0;
Rep(i,n) {
if(L[i] == -1) F[i] = 1;
else
F[i] = F[L[i]] + 1;
best >?= F[i];
}
printf("%d\n", best);
return 0;
}