(zjq)神犇一眼看出(AC)自动机 (Orz)
直接就讲做法了
首先对每个串建出(AC)自动机 将(fail)树找到 然后求出(dfs)序 我们发现一个单词 (S_i)是(S_j)的子串当且仅当(S_j)的某个前缀(T)通过(fail)树可以t跳到(S_i)的结束位置(感性理解一下,不太懂可以去找找特地讲(fail)树的博客) 我们记(f_i)为做到第(i)个串且(S_i)必选的最大值 则有
(f_i=max\{f_j+val[i]\}(j<i) (\&\&) (S_j) 的结束点是(S_i)某个前缀在(fail)树上的祖先())
我们发现这个过程可以在线段树上实现 对(fail)树的所有点建一颗线段树 通过(dfs)序来确定(fail)某个点所包含的区间 这样上述求(f_i)的过程就可以变成线段树区间修改,区间求最大值 就很好实现了
复杂度 (O(sum len * log(sum len)))
#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 1000000007
#define ll long long
#define mk make_pair
#define pb push_back
#define fi fisrt
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif
const int INF = 0x7fffffff;
const int N=2e4+5;
const int M=3e5+5;
typedef vector<int>::iterator iter;
vector<int>pos[N],e[M];
ll ans,tmp,t[M<<2],tag[M<<2];
int T,n,tot=1,rt=1,id,fail[M],c[M][26],w[N],len[N],in[M],out[M];
char s[M];
queue<int>q;
inline int read(){
int x=0,rev=0,ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return rev?-x:x;
}
void build(){
while(!q.empty()) q.pop();
q.push(rt);fail[rt]=1;
while(!q.empty()){
int now=q.front();q.pop();
for(int i=0;i<26;i++){
if(c[now][i]) fail[c[now][i]]=(now==1?1:c[fail[now]][i]),q.push(c[now][i]);
else c[now][i]=(now==1?1:c[fail[now]][i]);
}
}
}
void dfs(int x){
in[x]=++id;
for(iter it=e[x].begin();it!=e[x].end();it++) dfs(*it);
out[x]=id;
}
void pushdown(int x){
if(tag[x]){
t[x<<1]=max(t[x<<1],tag[x]),t[x<<1|1]=max(t[x<<1|1],tag[x]);
tag[x<<1]=max(tag[x<<1],tag[x]),tag[x<<1|1]=max(tag[x<<1|1],tag[x]);
tag[x]=0;
}
}
ll Query(int pos,int l,int r,int x){
// debug("l=%d r=%d
",l,r);
if(l==r) return t[pos];
int mid=l+r>>1;
pushdown(pos);
if(x<=mid) return Query(pos<<1,l,mid,x);
return Query(pos<<1|1,mid+1,r,x);
}
void modify(int pos,int l,int r,int nl,int nr,ll v){
// debug("l=%d r=%d nl=%d nr=%d
",l,r,nl,nr);
if(l>=nl&&r<=nr){
t[pos]=max(t[pos],v),tag[pos]=max(tag[pos],v);
return ;
}
pushdown(pos);
int mid=l+r>>1;
if(nl<=mid) modify(pos<<1,l,mid,nl,nr,v);
if(nr>mid) modify(pos<<1|1,mid+1,r,nl,nr,v);
t[pos]=max(t[pos<<1],t[pos<<1|1]);
}
int main(){
#ifdef Devil_Gary
freopen("in.txt","r",stdin);
#endif
T=read();
while(T--){
n=read(),id=ans=0,tot=1;
for(int i=1;i<=n;i++){
scanf("%s%d",s,&w[i]);
if(w[i]<=0) continue;
len[i]=strlen(s),pos[i].clear();
for(int j=0,p=1;j<len[i];j++){
int x=s[j]-'a';
if(!c[p][x]) c[p][x]=++tot;
p=c[p][x],pos[i].pb(p);
}
}
build();
for(int i=2;i<=tot;i++) e[fail[i]].pb(i);
dfs(1);
for(int i=1;i<=n;i++){
if(w[i]<=0) continue;
tmp=0;
for(int j=0;j<len[i];j++) tmp=max(tmp,Query(1,1,id,in[pos[i][j]]));
tmp+=w[i];ans=max(ans,tmp);
// bug(tmp);
modify(1,1,id,in[pos[i][len[i]-1]],out[pos[i][len[i]-1]],tmp);
}
printf("%lld
",ans);
cl(tag),cl(t),cl(fail),cl(c);
for(int i=1;i<=tot;i++) e[i].clear();
}
return 0;
}