注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

后缀树  

2013-11-22 21:44:47|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
hza手写版
抛开一切模板——好吧主要是我忘了模板怎么写的了——所以就贴在这儿了。。
觉得以前将边和点分开的做法很不清晰

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=1000000+10;
const int Alpha=26;

int INF=MAX-1,Del,Add;
char str[MAX];
LL ans=0;

struct Node
{
Node* ne[Alpha];
Node* fail,*p;//后缀链接
int l,r,nume;
Node(int a=0,int b=0,Node* father=0)
{
memset(ne,0,sizeof ne);
fail=0;
l=a,r=b;
p=father;
nume=0;
}

void set(int id,Node* t)
{
if(!ne[id])
++nume;
ne[id]=t;
}

pair<Node*,Node*> split(int L,int id,int len)
{
if(L==r-l)
{
Node* nleaf=new Node(len,INF,this);
set(id,nleaf);
ans-=len;
return mp(nleaf,this);
}

if(r!=INF)//ans-=r-l+1
ans-=r+1;
ans+=l;

Node * np=new Node(l,l+L,p);
ans+=L+1;

p->set(str[l],np);
np->set(str[l+L+1],this);
l=l+L+1;
if(r!=INF)
ans+=r+1;
ans-=l;

p=np;
Node* nleaf=new Node(len,INF,np);
np->set(id,nleaf);
ans-=len;
return mp(nleaf,np);
}
}*Root;

struct State
{
Node* u;
int L;

int check(int id)
{
if(L==u->r-u->l)
return u->ne[id]!=0;
else
return (str[u->l+L+1])==id;
}

void Go(int id)
{
if(L==u->r-u->l)
{
u=u->ne[id];
L=0;
}
else L++;
}

State Up()
{
State p;
p.u=u->p;
p.L=L;
int c=u->l;
if(p.u==Root && L==0)
return p;
if(p.u==Root)
{
p.L--;
c++;
p.u=p.u->fail->ne[(int)str[u->l+1]];
}
else
p.u=p.u->fail->ne[(int)str[c]];
for(;;)
{
int len=p.u->r-p.u->l+1;
if(p.L<len)
break;
c+=len;
p.L-=len;
p.u=p.u->ne[(int)str[c]];
}
return p;
}
}active;

queue<Node*> leaf_que;

void showEdge(Node* u)
{
int i;
REP(i,max(u->l,1),min( u->r, Add ))
cout<<char( str[i]+'a' );
cout<<" ";
}

Node* st[MAX];
int top;

void showTree(Node* u)
{
if(!u)
return;
int i;
st[++top]=u;
REP2(i,0,Alpha)
showTree(u->ne[i]);
if(u->r==MAX-1)
{
REP(i,2,top)
showEdge(st[i]);
cout<<endl;
}
--top;
}

void add(int len,int id)
{
Node* last=0;
for(;1;)
{
if(active.check(id))
{
if(last)
last->fail=active.u;
active.Go(id);
break;
}
pair<Node*,Node*> np=active.u->split(active.L,id,len);
if(last)
last->fail=np.y;
leaf_que.push(np.x);
if(active.u==Root)
break;
last=np.y;
active.u=np.y;
active=active.Up();
}
}

void del(int len)
{
Node* u=leaf_que.front();
leaf_que.pop();
len=len-Del+1;
int cc=0;
// showEdge(active.u);
// cout<<endl;
for(;u->nume==0 && u!=active.u;)
{
Node* p=u->p;
p->nume--;
p->ne[(int)str[u->l]]=0;
if(u->r!=INF)
ans-=u->r+1;
ans+=u->l;
len+=min(u->r,Add)-u->l+1;
delete u;
u=p;
}
if(u!=Root && u==active.u && u->nume==0)
{
if(u->r!=INF)
ans-=u->r+1;
ans+=u->l;

u->r=INF;
cc+=(min(u->r,Add)-u->l+1);
cc-=active.L+1;
u->l+=cc;
ans-=u->l;
leaf_que.push(u);
active=active.Up();
}
}

int main()
{
freopen("fqw.in","r",stdin);
freopen("fqw.out","w",stdout);
int n;
scanf("%d",&n);
Add=0,Del=1;
active.u=Root=new Node(0,0,0);
Root->p=0;
Root->fail=Root;
active.L=0;
while(n--)
{
char Q[10];
scanf("%s",Q);
if(Q[0]=='+')
{
scanf("%s",Q);
str[++Add]=Q[0]-'a';
add(Add,str[Add]);
}
else
{
/*
if(Add+Del+1-1==7)
showTree(Root);
*/
del(Add);
++Del;
}
cout<<ans+(LL)leaf_que.size()*(Add+1)<<endl;
/*
if(Add+Del-1==7)
showTree(Root);
*/
}
return 0;
}



  评论这张
 
阅读(597)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017