簡單來說，就是給你一個固定的字串集合$A$和不固定的字串集合$B$
操作$1$就是把一個字串加入$B$
操作$2$就是給你$i$，問你$A_{i}$是$B$中幾個$B_{k}$的子字串
首先，我們可以把$A$建成一個$AC$自動機
這樣當$B$加入一個新字串之後，就可以馬上和$A$進行匹配，找出$A$中哪幾個是這個新字串的子字串了
當然，不能直接沿著失配函數$fail$ (也有人稱作$next$) 直接更新$A$中每個$A_{i}$的計數器
我們必須想到一個巧妙的方法，讓所有被匹配到的$A_{i}$和其沿著$fail$往上的所有$A_{k}$一起被加$1$ (因為$A_{i}$匹配意味著其沿著$fail$往上的所有$A_{k}$也會匹配成功)
可以發現，如果將所有的$u\rightarrow fail[u]$邊反向成$fail[u]\rightarrow u$，然後建圖
我們會得到一棵根為$0$的樹 (稱作$fail\ tree$好了)
而上述操作就是將一堆節點和它們的祖先們全部加$1$
利用線段樹維護樹壓平的序列，就可以實現$O(\log N)$查詢某個節點的值、$O(\log N)$一次將某個節點和其所有的祖先們加$1$了
(方法是查尋的時候直接查詢整棵子樹加$1$的總次數，修改只需單點修改即可)
可是這樣有可能會造成某個祖先被多次加$1$的情況
可以發現，當某個節點被加$1$第二次，那麼這個節點的祖先們也都會被這個多加的$1$影響到
那就把多加的扣回來就好啦
我們可以將這一堆要讓自己和祖先們都加$1$的節點依照$fail\ tree$的$dfs$順序排序
假設排序完的序列是$\{v_{1},v_{2},v_{3},...,v_{n}\}$
對於每個$1\leq i\leq n$，將所有$v_{i}$及其祖先們都加$1$
對於每個$2\leq i\leq n$，將所有$LCA(v_{i-1},v_{i})$ ($Lowest\ Common\ Ancestor$) 及其祖先們都減$1$
這樣就剛好讓每個被影響到的點都恰好加$1$了
($\left|A\right|$代表集合$A$裡面所有的字串長度總和)
在$B$中加入一個字串$s$的複雜度：$O(\left|s\right|\log\left|A\right|)$
查詢的時間複雜度：$O(\log\left|A\right|)$
p.s.這個code沒有特別優化，在自己的電腦實測是$8$秒 (如下圖)，而時限是$4$秒
2016/2/27 15:54更新：後來找到judge可以傳了，這份code不意外地獲得了TLE，優化後的code在這裡
時間複雜度：$O(Q\log\left|A\right|+\left|B_{final}\right|\log\left|A\right|)$
code:
#include<cstdio> #include<cassert> #include<vector> #include<map> #include<queue> #include<algorithm> #include<ctime> using namespace std; struct SegTree { int n; vector<int>sum; void Build(const int id,const int l,const int r) { while(id>=(int)sum.size())sum.push_back(0); sum[id]=0; if(l<r) { const int mid=(l+r)/2; Build(id*2,l,mid),Build(id*2+1,mid+1,r); } } void Build(const int _n){n=_n;Build(1,0,n-1);} void Modify(const int id,const int l,const int r,const int loc,const int val) { sum[id]+=val; if(l<r) { const int mid=(l+r)/2; if(loc<=mid)Modify(id*2,l,mid,loc,val); else Modify(id*2+1,mid+1,r,loc,val); } } void Modify(const int loc,const int val){Modify(1,0,n-1,loc,val);} int Query(const int id,const int l,const int r,const int bl,const int br) { if(r<bl||br<l)return 0; if(bl<=l&&r<=br)return sum[id]; const int mid=(l+r)/2; return Query(id*2,l,mid,bl,br)+Query(id*2+1,mid+1,r,bl,br); } int Query(const pair<int,int>&p){return Query(1,0,n-1,p.first,p.second);} }; struct TreeSequence { vector<vector<int> >et,parents; vector<pair<int,int> >segs; vector<int>deps; void Clear(const int n) { et.clear(),segs.clear(),parents.clear(),deps.clear(); et.resize(n),segs.resize(n),parents.resize(n),deps.resize(n); } void Build(const int u,const int parent,const int dep,int &clock) { deps[u]=dep; parents[u].clear(); if(parent!=-1) { for(int cur=parent,i=0;;cur=parents[cur][i++]) { parents[u].push_back(cur); if(i>=(int)parents[cur].size())break; } } segs[u].first=clock; for(const int nxt:et[u])Build(nxt,u,dep+1,clock); segs[u].second=clock++; } int LowestCommonAncestor(int a,int b) { if(deps[a]<deps[b])swap(a,b); for(int i=30,dis=deps[a]-deps[b];i>=0;i--)if(dis&(1<<i))a=parents[a][i]; assert(deps[a]==deps[b]); if(a==b)return a; for(int i=30;i>=0;i--)if((1<<i)<=deps[a]&&parents[a][i]!=parents[b][i])a=parents[a][i],b=parents[b][i]; assert(parents[a][0]==parents[b][0]); return parents[a][0]; } const pair<int,int>&operator[](const int i)const{return segs[i];} }; struct AC_Automaton { int sz; vector<map<char,int> >ch; vector<bool>is_end; void Clear(){sz=0;ch.clear(),is_end.clear();Expand();} void Expand(){ch.push_back(map<char,int>()),is_end.push_back(false);sz++;} int GetNxt(const int u,const char c) { const auto &it=ch[u].find(c); if(it==ch[u].end()){Expand();return ch[u][c]=sz-1;} else return it->second; } int Insert(const char *str) { int u=0; for(int i=0;str[i];i++)u=GetNxt(u,str[i]); is_end[u]=true; return u; } vector<int>fail; void BuildFail() { fail.clear(),fail.resize(sz,0); queue<int>q; for(const auto &it:ch[0])q.push(it.second); while(!q.empty()) { const int u=q.front();q.pop(); for(const auto &it:ch[u]) { int &f=fail[it.second]=fail[u]; while(f&&ch[f].find(it.first)==ch[f].end())f=fail[f]; if(true) { const auto &iu=ch[f].find(it.first); if(iu!=ch[f].end())f=iu->second; } if(is_end[f])is_end[it.second]=true; q.push(it.second); } } } TreeSequence seq; SegTree seg_tree; void BuildFailTree() { seq.Clear(sz); for(int i=1;i<sz;i++)seq.et[fail[i]].push_back(i); int clock=0; seq.Build(0,-1,0,clock); assert(clock==sz); seg_tree.Build(sz); } void Match(const char *str) { // static int kase=0;kase++; int u=0; vector<int>nodes; for(int i=0;str[i];i++) { while(u&&ch[u].find(str[i])==ch[u].end())u=fail[u]; const auto it=ch[u].find(str[i]); if(it!=ch[u].end())u=it->second; if(is_end[u])nodes.push_back(u); } if(nodes.empty())return; sort(nodes.begin(),nodes.end(),[this](const int a,const int b)->bool{return seq[a].second<seq[b].second;}); seg_tree.Modify(seq[nodes[0]].second,1); for(int i=1;i<(int)nodes.size();i++) { seg_tree.Modify(seq[nodes[i]].second,1); seg_tree.Modify(seq[seq.LowestCommonAncestor(nodes[i-1],nodes[i])].second,-1); } } int Query(const int u){return seg_tree.Query(seq[u]);} }AC; int N; int main() { freopen("inn.txt","r",stdin); freopen("out.txt","w",stdout); // clock_t start_time; while(scanf("%d",&N)==1) { // start_time=clock(); AC.Clear(); vector<int>nodes; for(int i=0;i<N;i++) { static char str[2000001]; scanf("%s",str); nodes.push_back(AC.Insert(str)); } AC.BuildFail(); AC.BuildFailTree(); int querycount;scanf("%d",&querycount); for(int type,val;querycount--;) { scanf("%d",&type); if(type==1) { static char str[2000001]; scanf("%s",str); AC.Match(str); } else if(type==2) { scanf("%d",&val); printf("%d\n",AC.Query(nodes[--val])); } else assert(0); } // printf("run time = %.3f s.\n",(double)(clock()-start_time)/CLOCKS_PER_SEC); } return 0; }
沒有留言:
張貼留言
歡迎留言或問問題～
若您的留言中包含程式碼，請參考這篇
如果留言不見了請別慌，那是因為被google誤判成垃圾留言，小莫會盡快將其手動還原
注意：只有此網誌的成員可以留言。