2011年成都赛区G题的题解。
很容易想到一个朴素的，O(n^2)的动态规划（把做KMP的时间当做常数）。
显然，这样做太慢了，要想想应该怎么优化。
关于字符串的匹配，很容易想到用后缀数组来优化。
但是只用后缀数组的话，还是没有用的。
要优化转移使每次转移的代价由O(n)变成O(logn)甚至O(1)。那么时间复杂度就自然降低了。
于是很容易就想到了线段树。
接着，把它们组合起来。
首先把输入的所有字符串连接起来，中间用’#’分割（这样可以减少用倍增法做后缀数组的时间复杂度的，不添加的话会超时，不过如果你是用其他一些O(n)的算法来构造后缀数组或者后缀树的话就可以不用分割）。
再做后缀数组。
然后开始动规。
用f[i]表示第一个单词为word[i]的最优解。
那么f[i]=max{f[j]|j>i and word[i] is a substring of word[j]}+W[i]，可以用线段树来优化max操作。
设suffix(i)表示从第i位到最后所构成的后缀，rank[i]表示suffix(i)的排名，p[i]表示word[i]在拼接后的字符串中的位置，用len[i]表示word[i]的长度。
线段树记录排名在某个区间的所有串的开头部分(即’#’前部分)所在单词的f值。
求f[i]时，用二分法（需要利用高度数组，并需要用到RMQ）求得L=min{i|LCP(suffix(SA[j]),suffix(p[i]))=len[i]}，R=max{i|LCP(suffix(SA[j]),suffix(p[i]))=len[i]}。
然后f[i]=排名在L到R之间的所有f的最大值+W[i]，这一步用线段树来求。
最后更新线段树，将排名为rank[p[i]+j](0<=j<len[i])的f值更新为f[i]。
这道题就做出来了。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-10
DESCRIPTION:
$DESCRIPTION
*/
#include <cstdio>
#include <cstring>
using namespace std;
namespace sujiaos_lab
{
const int LOG2_MAXLENGTH=19;
const int MAXLENGTH=320003;
const int MAXALPHABET=129;
typedef char string[MAXLENGTH];
typedef int* int_pointer;
int_pointer sort;
int _SA[MAXLENGTH],_rank[MAXLENGTH],_TSA[MAXLENGTH],_Trank[MAXLENGTH];
int_pointer SA=_SA,rank=_rank,TSA=_TSA,Trank=_Trank;
void get_SA(string s,int length)
{
sort=Trank;
for (int i=0;i<MAXALPHABET;i++) sort[i]=0;
for (int i=1;i<=length;i++) sort[s[i]]++;
for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];
for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;
rank[SA[1]]=1;
for (int i=2;i<=length;i++)
if (s[SA[i]]==s[SA[i-1]]) rank[SA[i]]=rank[SA[i-1]];
else rank[SA[i]]=rank[SA[i-1]]+1;
for (int block=1;rank[SA[length]]!=length;block<<=1)
{
sort=Trank;
for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;
for (int i=length;i>=1;i–)
if (SA[i]-block>=1)
TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;
for (int i=length-block+1;i<=length;i++)
TSA[sort[rank[i]]–]=i;
int_pointer swap;
swap=SA,SA=TSA,TSA=swap;
swap=rank,rank=Trank,Trank=swap;
rank[SA[1]]=1;
for (int i=2;i<=length;i++)
if (Trank[SA[i]]==Trank[SA[i-1]]
&&Trank[SA[i]+block]==Trank[SA[i-1]+block])
rank[SA[i]]=rank[SA[i-1]];
else rank[SA[i]]=rank[SA[i-1]]+1;
}
}
int_pointer height;
void get_height(string s,int length)
{
height=TSA;
for (int i=1,h=0;i<=length;i++)
{
if (h) h–;
if (rank[i]!=1)
{
int j=SA[rank[i]-1];
while (s[i+h]==s[j+h]) h++;
}
height[rank[i]]=h;
}
}
int_pointer log2;
int rmq[LOG2_MAXLENGTH][MAXLENGTH];
void get_RMQ(int length)
{
log2=Trank;
log2[1]=0;
for (int i=2;i<=length;i++) log2[i]=log2[i-1]+(i==(i&(-i)));
for (int i=1;i<=length;i++) rmq[0][i]=i;
for (int log=1;log<=log2[length];log++)
{
int exp=1<<log,exp_div_2=exp>>1;
for (int i=1;i<=length-exp+1;i++)
{
int a=rmq[log-1][i];
int b=rmq[log-1][i+exp_div_2];
rmq[log][i]=height[a]<height[b]?a:b;
}
}
}
int RMQ(int a,int b)
{
int log=log2[b-a+1];
int exp=1<<log;
a=rmq[log][a],b=rmq[log][b-exp+1];
return height[a]<height[b]?a:b;
}
int LCP(int a,int b)
{
a=rank[a],b=rank[b];
if (a>b) return height[RMQ(b+1,a)];
else return height[RMQ(a+1,b)];
}
}
using namespace sujiaos_lab;
const int MAXN=20003;
sujiaos_lab::string s;
int W[MAXN];
int p[MAXN];
int len[MAXN];
const int MAXNODE=MAXLENGTH*4+1;
int st[MAXNODE];
void insert(int p,int value,int L,int R,int root=1)
{
if (p<L||R<p) return;
else
{
if (value>st[root])
st[root]=value;
if (L==R) return;
int LL=L,LR=(L+R)>>1,Lroot=root<<1,
RL=LR+1,RR=R,Rroot=Lroot|1;
insert(p,value,LL,LR,Lroot);
insert(p,value,RL,RR,Rroot);
}
}
int query(int l,int r,int L,int R,int root=1)
{
if (r<L||R<l||L>R) return 0;
else if (l<=L&&R<=r) return st[root];
else
{
int LL=L,LR=(L+R)>>1,Lroot=root<<1,
RL=LR+1,RR=R,Rroot=Lroot|1;
int LV=query(l,r,LL,LR,Lroot);
int RV=query(l,r,RL,RR,Rroot);
return LV>RV?LV:RV;
}
}
int main()
{
int TC;
scanf(“%d”,&TC);
for (int tc=1;tc<=TC;tc++)
{
int N;
scanf(“%d”,&N);
for (int i=1;i<=N;i++)
{
p[i]=p[i-1]+len[i-1];
s[p[i]++]=’#’;
scanf(“%s%d”,s+p[i],&W[i]);
len[i]=strlen(s+p[i]);
}
int length=strlen(s);
get_SA(s,length);
get_height(s,length);
get_RMQ(length);
int answer=0;
memset(st,0,sizeof(st));
for (int i=N;i>=1;i–)
{
int L,R,l,r;
L=0,R=rank[p[i]];
while (L+1!=R)
{
int mid=(L+R)>>1;
if (height[RMQ(mid+1,rank[p[i]])]>=len[i]) R=mid;
else L=mid;
}
l=R;
L=rank[p[i]],R=length+1;
while (L+1!=R)
{
int mid=(L+R)>>1;
if (height[RMQ(rank[p[i]]+1,mid)]>=len[i]) L=mid;
else R=mid;
}
r=L;
int get=query(l,r,1,length)+W[i];
if (get>answer) answer=get;
for (int j=0;j<len[i];j++)
insert(rank[p[i]+j],get,1,length);
}
printf(“Case #%d: %d\n”,tc,answer);
}
}
