The 2011 ACM-ICPC ACRC]G.GRE Words(二)
}
int ask(int l, int r) {return nL = l, nR = r, ans = 0, query(nRT), ans;}
void prepare()
{
tt = root, memset(root, 0, sizeof root);
adj = es, memset(lst, 0, sizeof lst);
nt = ns;
}
char st[maxn]; int w[maxk];
int main()
{
#ifndef ONLINE_JUDGE
freopen("p3.in", "r", stdin);
freopen("p3.out", "w", stdout);
#endif
for (scanf("%d", &T); T--; ) {
int i, ans = 0;
prepare(), scanf("%d", &n);
FOR(i, 1, n) scanf("%s%d", st, w + i), insert(st, i);
build();
dfs();
build(nRT, 1, cnt);
ROF(i, n, 1) {
int k = ask(begin[i], end[i]) + w[i];
maxim(ans, k);
for (trie *p = tback[i]; p != root; p = p->fa)
insert(mark[p - root], k);
}
printf("%d\n", ans);
}
return 0;
}
后缀数组code:
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif
#define PI M_PI
#define oo 0x13131313
#define PB push_back
#define PO pop_back
#define iter iterator
#define MP make_pair
#define fst first
#define snd second
#define cstr(a) (a).c_str()
#define FOR(i, j, k) for (i = (j); i <= (k); ++i)
#define ROF(i, j, k) for (i = (j); i >= (k); --i)
#define FER(i, j, k) for (i = j[k]; i; i = i->n)
#define FRE(i, a) for (i = (a).begin(); i != (a).end(); ++i)
typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;
typedef long double real;
template inline bool minim(T &a, const T &b) {return b < a a = b, 1 : 0;}
template inline bool maxim(T &a, const T &b) {return b > a a = b, 1 : 0;}
template inline T sqr(const T &a) {return a * a;}
#define maxn 300005
#define maxk 20005
#define maxm 2005
typedef int array[maxn];
typedef int arr[maxk];
array sa, rank, sum, xx, yy, z, height, st;
void build(int &n, int &m)
{
int i, j, k; int *x = xx, *y = yy;
memset(sum, 0, sizeof(array));
FOR(i, 1, n) ++sum[x[i] = st[i]];
FOR(i, 2, m) sum[i] += sum[i - 1];
ROF(i, n, 1) sa[sum[x[i]]--] = i;
for (j = 1; m < n; j <<= 1, m = k) {
k = 0;
FOR(i, n - j + 1, n) y[++k] = i;
FOR(i, 1, n) if (sa[i] > j) y[++k] = sa[i] - j;
memset(sum, 0, sizeof(array));
FOR(i, 1, n) ++sum[z[i] = x[y[i]]];
FOR(i, 2, m) sum[i] += sum[i - 1];
ROF(i, n, 1) sa[sum[z[i]]--] = y[i];
swap(x, y), x[sa[1]] = k = 1;
FOR(i, 2, n) {
int p = sa[i], q = sa[i - 1];
x[p] = y[p] == y[q] && y[p + j] == y[q + j] k : ++k;
}
}
memcpy(rank, x, sizeof(array));
FOR(i, 1, n) {
j = sa[rank[i] - 1];
z[i] = z[i - 1] z[i - 1] - 1 : 0;
for (; st[i + z[i]] == st[j + z[i]]; ++z[i]);
height[rank[i]] = z[i];
}
}
int back[200], L, ans;
array belong;
arr w, len, begin, end;
void init(int &n, int &m)
{
int i, j, k;
memset(back, 0, sizeof back);
scanf("%d\n", &n), m = n;
int *ptr = st;
FOR(i, 1, n) {
begin[i] = k = j = ptr - st + 1;
for (*(++ptr) = getchar(); 'a' <= *ptr && *ptr <= 'z'; *(++ptr) = getchar()) {
if (!back[*ptr]) back[*ptr] = ++m;
*ptr = back[*ptr];
belong[k] = i, ++k;