题解:http://www.cnblogs.com/swm8023/archive/2012/08/08/2627535.html
要输出路径,价值最大优先,价值相同的取长度较小者,仍相同取字典序较小者。
这里将模式串倒着插进AC自动机,就将前缀比较转化成后缀比较。所以开个数组记录从哪个点转移过来以后,就可以逆推回去比较字典序大小了。
#include<cstdio> #include<cstring> #include<queue> using namespace std; queue<int>q; int child[1200][26],fail[1200],size,ma[1200],f[60][1200],ans,path[60][1200]; int val[1200]; char c[1200]; void Insert(char S[],int x) { int len=strlen(S); int now=0; for(int i=len-1;i>=0;--i) { if(!child[now][S[i]-'a']) { child[now][S[i]-'a']=size++; c[child[now][S[i]-'a']]=S[i]; } now=child[now][S[i]-'a']; } val[now]+=x; } void build() { fail[0]=-1; q.push(0); while(!q.empty()) { int U=q.front(); q.pop(); for(int i=0;i<26;++i) if(child[U][i]) { int V=fail[U]; while(V!=-1) { if(child[V][i]) { fail[child[U][i]]=child[V][i]; break; } V=fail[V]; } if(V==-1) fail[child[U][i]]=0; val[child[U][i]]+=val[fail[child[U][i]]]; q.push(child[U][i]); } else if(U) child[U][i]=child[fail[U]][i]; } } void Init() { memset(child,0,sizeof(child)); memset(fail,0,sizeof(fail)); memset(val,0,sizeof(val)); memset(c,0,sizeof(c)); size=1; } char s[110][13]; int T,n,m; bool cmp(int Length,int U,int V) { while(Length) { if(c[U]!=c[V])return c[U]<c[V]; U=path[Length][U]; V=path[Length][V]; --Length; } return 0; } int main() { // freopen("hdu2296.in","r",stdin); int X; scanf("%d",&T); for(;T;--T) { Init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) scanf("%s",s[i]); for(int i=1;i<=m;++i) { scanf("%d",&X); Insert(s[i],X); } build(); memset(f,-1,sizeof(f)); f[0][0]=0; for(int i=0;i<n;++i) for(int j=0;j<size;++j) { if(f[i][j]==-1) continue; for(int k=0;k<26;++k) if(f[i+1][child[j][k]]<f[i][j]+val[child[j][k]]) { path[i+1][child[j][k]]=j; f[i+1][child[j][k]]=f[i][j]+val[child[j][k]]; } else if(f[i+1][child[j][k]]==f[i][j]+val[child[j][k]] && cmp(i,j,path[i+1][child[j][k]])) path[i+1][child[j][k]]=j; } int ansl=-1,ansid; for(int i=0;i<=n;++i) for(int j=0;j<size;++j) if(ansl==-1 || f[i][j]>f[ansl][ansid] || (i==ansl && f[i][j]==f[ansl][ansid] && cmp(i,j,ansid))) { ansl=i; ansid=j; } while(ansl) { putchar(c[ansid]); ansid=path[ansl][ansid]; --ansl; } puts(""); } return 0; }