AC自动机fail树上dfs序建线段树+动态memset清空

题意：http://acm.hdu.edu.cn/showproblem.php?pid=4117

思路：https://blog.csdn.net/u013306830/article/details/77586562

主要就是卡你内存，AC自动机的字典树得要用了再清空。
代码有点长吧。。。
 #include <cstdio>//sprintf islower isupper

 #include <iostream>//pair

 #include <string.h>//strstr substr strcat

 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less

 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation

 #define mem(a,b) memset(a,b,sizeof(a))

 #define pr printf

 #define sc scanf

 #define ls rt<<1

 #define rs rt<<1|1

 const int N=3e5+;

 char s[N];

 int pos[],val[];

 //-------------------------------

 class mymap

 {

 public:

     int tot;

     int head[N];

     int SZ[N];

     int dfn[N],cnt;

     struct

     {

         int to,next;

     }edge[N];

     void Init(int n)

     {

         tot=;

         cnt=-;

         for(int i=;i<=n;++i)

             head[i]=SZ[i]=;

     }

     void add(int from,int to)

     {

         ++tot;

         edge[tot].to=to;

         edge[tot].next=head[from];

         head[from]=tot;

     }

     int dfs(int u)

     {

         ++cnt;

         dfn[u]=cnt;

         SZ[dfn[u]]=;

         for(int i=head[u];i;i=edge[i].next)

         {

         //    cout<<edge[i].first<<endl;

             SZ[dfn[u]]+=dfs(edge[i].to);

         }

         return SZ[dfn[u]];

     }

 }TREE;

 class seg_tree

 {

 public:

     int max_[N<<],add[N<<];

     void up(int rt)

     {

         max_[rt]=max(max_[ls],max_[rs]);

     }

     void dn(int rt)

     {

         if(add[rt])

         {

             add[ls]=max(add[ls],add[rt]);

             add[rs]=max(add[rs],add[rt]);

             max_[ls]=max(max_[ls],add[rt]);

             max_[rs]=max(max_[rs],add[rt]);

             add[rt]=;

         }

     }

     void Build(int l,int r,int rt)

     {

         max_[rt]=;

         add[rt]=;

         if(l==r)

         {

             return;

         }

         int mid=(l+r)>>;

         Build(l,mid,rt<<);

         Build(mid+,r,rt<<|);

     }

     int Q_dot(int pos,int l,int r,int rt)

     {

         if(l==r)

         {

             return max_[rt];

         }

         int mid=(l+r)>>;

         dn(rt);

         if(pos<=mid)

             return Q_dot(pos,l,mid,rt<<);

         else

             return Q_dot(pos,mid+,r,rt<<|);

     }

     void update_qu(int L,int R,int V,int l,int r,int rt)

     {

         if(L>R)return;

         if(L<=l&&r<=R)

         {

             max_[rt]=max(max_[rt],V);

             add[rt]=max(add[rt],V);

             return;

         }

         int mid=(l+r)>>;

         dn(rt);

         if(L<=mid)

             update_qu(L,R,V,l,mid,rt<<);

         if(R>mid)

             update_qu(L,R,V,mid+,r,rt<<|);

         up(rt);

     }

 }SEG;

 class ac_automaton

 {

 public:

     int tot;

     int trie[N][];

     int fail[N];

     //other

     //--------------

     void Insert(int l,int r)

     {

         int rt=;

         for(int i=l;i<=r;++i)

         {

             int id=s[i]-'a'+;

             if(!trie[rt][id])

             {

                 mem(trie[++tot],);

                 trie[rt][id]=tot;

             }

             rt=trie[rt][id];

         }

     }

     queue<int>q;

     void Getfail()

     {

         for(int i=;i<=;++i)

         {

             int id=trie[][i];

             if(id)

             {

                 fail[id]=;

                 q.push(id);

             }

         }

         while(!q.empty())

         {

             int rt=q.front();q.pop();

             for(int i=;i<=;++i)

             {

                 int id=trie[rt][i];

                 if(id)

                 {

                     fail[id]=trie[fail[rt]][i];

                     q.push(id);

                 }

                 else

                     trie[rt][i]=trie[fail[rt]][i];

             }

         }

     }

     int Find(int l,int r,int id,int n)

     {

         int rt=;

         int pos=;

         int temp_max=;

         for(int i=l;i<=r;++i)

         {

             rt=trie[rt][s[i]-'a'+];

             pos=TREE.dfn[rt];

             int temp_val=SEG.Q_dot(pos,,n,)+val[id];

             temp_max=max(temp_max,temp_val);

         }

         SEG.update_qu(pos,pos+TREE.SZ[pos]-,temp_max,,n,);

     //    for(int j=1;j<=n;++j)pr("%d ",SEG.Q_dot(j,1,n,1));

     //    cout<<endl<<"----------------------------------"<<endl;

         return temp_max;

     }

 }AC;

 void solve()

 {

     AC.tot=;

     mem(AC.trie[],);

     int n,tot;

     sc("%d",&n);

     pos[]=;

     for(int i=;i<=n;++i)

     {

         sc("%s %d",s+pos[i],&val[i]);

         int l=strlen(s+pos[i]);

         AC.Insert(pos[i],pos[i]+l-);

         pos[i+]=pos[i]+l;

     }

     tot=AC.tot;

 //    pr("%s\n",s+1);

     AC.Getfail();

     TREE.Init(tot);

     SEG.Build(,tot,);

     for(int i=;i<=AC.tot;++i)

         TREE.add(AC.fail[i],i);

     TREE.SZ[]=TREE.dfs();

     int ans=;

     for(int i=;i<=n;++i)

         ans=max(ans,AC.Find(pos[i],pos[i+]-,i,tot));

     pr("%d\n",ans);

 }

 int main()

 {

     int T,cnt=;

     sc("%d",&T);

     while(T--)

     {

         pr("Case #%d: ",++cnt);

         solve();

     }

     return ;

 }

 /**************************************************************************************/
巴特西

AC自动机fail树上dfs序建线段树+动态memset清空

题意：http://acm.hdu.edu.cn/showproblem.php?pid=4117

思路：https://blog.csdn.net/u013306830/article/details/77586562

最新文章

热门文章
