HDU 4117 GRE Words【AC自动机+线段树】
和这题有些类似。
AC自动机。
字符串匹配算法，大概就是kmp，ac自动机，后缀数组，后缀自动机这么几种了。对于这题，我们很容易想到暴力dp，用kmp去匹配，总复杂度可以做到 o(n2+2∗m) （n为字符串个数，m为所有字符串的总长），但这样还不够，超时妥妥的。
那就要考虑怎么维护这个dp了。
把自动机建好后，从前往后一个个的，去匹配。在自动机上匹配的过程中，我们可以发现，这个串走到的所有的节点，以及这些节点一路往根fail的节点，都是这个串的子串，那么以这个串结尾的获得的importance最大值，就是这所有节点的importance最大值，加上当前枚举的串的权值了。
然而，我们如果在匹配的过程中，一直fail走，那么，超时也是妥妥的， m2 的数据还是能构造出来的。因此，我们要考虑的是怎么维护这个最大值了。
我们根据fail指针连边，会构成一颗fail树，fail树上，父亲节点是它子树所表示的串的后缀。那么对于当前串走到的某一个节点，他的最大值，就是fail树上，从他到根的这条链上的最大值了。
那么当我们得到以某一个字符串为结尾的序列，能得到的最大值时，我们能影响到哪些节点的最值呢？
很显然，fail树上，该节点的子树都会受到影响，那么就好办了。一颗子树，根据dfs序，是一段连续的区间，根据这个，我们就可以构造线段树了。区间更新，单点询问最大值就ok了。
// whn6325689
// Mr.Phoebe
// http://blog.csdn.net/u013007900
#include pll;
typedef complex point;
typedef pair<int, int> pii;
typedef pairint> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define getidx(l,r) (l+r | l!=r)
#define ls getidx(l,mid)
#define rs getidx(mid+1,r)
#define lson l,mid
#define rson mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=300010;
const int MAC=26;char s[MAXN],ca[MAXN];
int id[MAXN],val[MAXN];struct Node
{ int mx,la;
}t[MAXN<<1];void build(int l,int r)
{int idx=getidx(l,r),mid=MID(l,r);t[idx].la=t[idx].mx=0;if(l==r) return;build(lson);build(rson);
} void pushdown(int l,int r)
{int idx=getidx(l,r),mid=MID(l,r);if(!t[idx].la) return;t[ls].mx=max(t[ls].mx,t[idx].la);t[rs].mx=max(t[rs].mx,t[idx].la);t[ls].la=max(t[ls].la,t[idx].la);t[rs].la=max(t[rs].la,t[idx].la);t[idx].la=0;
}void update(int l,int r,int L,int R,int v)
{int idx=getidx(l,r),mid=MID(l,r); if(L==l && r==R){t[idx].la=max(t[idx].la,v);t[idx].mx=max(t[idx].mx,v);return; }pushdown(l,r);if(R<=mid) update(l,mid,L,R,v);else if(L>mid) update(mid+1,r,L,R,v);else{update(l,mid,L,mid,v);update(mid+1,r,mid+1,R,v);}
}int query(int l,int r,int pos)
{int idx=getidx(l,r),mid=MID(l,r); if(l==r)return t[idx].mx;pushdown(l,r);if(pos<=mid) return query(l,mid,pos);else return query(mid+1,r,pos);
}int dfn[MAXN],rdfn[MAXN];
int timestamp;struct Tree
{struct Edge{int to,next;}e[MAXN];int head[MAXN],tot;void init(){CLR(head,-1);tot=1;}void addedge(int u,int v){e[tot].to=v;e[tot].next=head[u];head[u]=tot++;}void dfs(int u){dfn[u]=++timestamp;for(int i=head[u];~i;i=e[i].next)dfs(e[i].to);rdfn[u]=timestamp;}
}tree;struct AC
{int ch[MAXN][MAC],f[MAXN],size;void init(){size=0;f[0]=0;newnode(0);}int newnode(int pre){CLR(ch[size],0);return size++;} void insert(char *S){int u=0,x;for(char *sp=S;*sp;sp++){x=*sp-'a';if(!ch[u][x]) ch[u][x]=newnode(u);u=ch[u][x];}}int que[MAXN],front,back;void getfail(){int u,cur;front=back=0;for(int i=0;iif(ch[0][i]){que[back++]=ch[0][i];f[ch[0][i]]=0;}while(frontfor(int i=0;iif(u){que[back++]=u;f[u]=ch[f[cur]][i];}elsech[cur][i] = ch[f[cur]][i];}} tree.init();for(int i=1;i0;tree.dfs(0);}int solve(char *S) { int len=strlen(S);int u=0,now=0,ans=0; build(1,timestamp); for(int i=0;i'a']; int valu=query(1,timestamp,dfn[u]); now=max(now,valu); if(id[i]) { if(val[id[i]]>0) now+=val[id[i]]; ans=max(ans,now); update(1,timestamp,dfn[u],rdfn[u],now); u=now=0; } } return ans; }
}ac;int main()
{ int len,n,m,T,cas=1; scanf("%d",&T); while(T--) { scanf("%d",&n); len=0; ac.init(); CLR(id,0); for(int i=1;i<=n;i++) { scanf("%s%d",ca,&val[i]); ac.insert(ca); int l=strlen(ca); for(int j=0;j1]=i; } ac.getfail(); printf("Case #%d: %d\n",cas++,ac.solve(s)); } return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！