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

Download