【AC自动机】【动态规划】hdu2296 Ring

题解：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;

}