Codeforces 163 E&HDU 4117&Noi 2011タヌキのタイプライター&&boj 1602

http://codeforces.com/problemset/problem/163/E
http://acm.hdu.edu.cn/showproblem.php?pid=4117
http://61.187.179.132/JudgeOnline/problem.php?id=2434
http://n.boj.me/onlinejudge/newoj/showProblem/show_problem.php？problem_id=1602
この四つの問題は全部データ構造で保護されたAC自動機です。
基本的な考え方はACの自動機を作ってから、ついでにfailツリーを作って、線分樹でメンテナンスします。
基本的な原理：あるノードからfailポインタに沿ってルートノードの過程で出会うノードはすべて改行の接尾辞と同じ列になりますが、failポインタはfailツリーを構成しています。だから、一つの列はどのような接尾文字列かもしれませんか？答えは、ノードがfailツリーの中の1つのツリーに対応することです。
Codeforces 163 E

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 1000100
using namespace std;

char S[N];//     S 
int str[N],mp[N],vis[N];//              ，mp[i]   i         ，
int pos;
int next[N][26],fail[N],flag[N];

int newnode(){
    memset(next[pos],0,sizeof(next[pos]));
    fail[pos]=flag[pos]=0;
    return pos++;
}

void insert(char * s,int id){
    int p=0,i=0;
    for(;s[i];i++){
        int k=s[i]-'a';
        p=next[p][k]?next[p][k]:next[p][k]=newnode();
    }
    flag[p]=1;
    mp[id]=p;
}

void makefail(){
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int v=next[u][i];
            if(v==0) next[u][i]=next[fail[u]][i];
            else q.push(v);
            if(v && u)fail[v]=next[fail[u]][i];
        }
    }
}

struct Tree{
    int l,r;
    int add;
    int sum;
}tree[N<<2];

void build(int s,int t,int id){
    tree[id].l=s;
    tree[id].r=t;
    tree[id].add=tree[id].sum=0;
    if(s!=t){
        int mid=(s+t)>>1;
        build(s,mid,id<<1);
        build(mid+1,t,id<<1|1);
    }
}

void update(int s,int t,int add,int id){
    //printf("%d %d %d
",s,t,id);
    if(tree[id].l==s && tree[id].r==t){
        tree[id].add+=add;
        tree[id].sum+=add;
        return ;
    }
    if(tree[id].add!=0){
        tree[id<<1].add+=tree[id].add;
        tree[id<<1|1].add+=tree[id].add;
        tree[id<<1].sum+=tree[id].add;
        tree[id<<1|1].sum+=tree[id].add;
        tree[id].add=0;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(t<=mid) update(s,t,add,id<<1);
    else if(mid<s) update(s,t,add,id<<1|1);
    else{
        update(s,mid,add,id<<1);
        update(mid+1,t,add,id<<1|1);
    }
}

int query(int POS,int id){
    if(tree[id].l==tree[id].r){
        return tree[id].sum;
    }
    if(tree[id].add!=0){
        tree[id<<1].add+=tree[id].add;
        tree[id<<1|1].add+=tree[id].add;
        tree[id<<1].sum+=tree[id].add;
        tree[id<<1|1].sum+=tree[id].add;
        tree[id].add=0;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(POS<=mid) return query(POS,id<<1);
    else return query(POS,id<<1|1);
}

struct Edge{
    int v,next;
}edge[N*2];
int head[N],cnt;
int tim[N],son[N],dep;//tim[i]    i    dfs 

void init(){
    memset(head,-1,sizeof(head));
    cnt=dep=0;
}

void addedge(int u,int v){
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

void dfs(int u,int fa){
    tim[u]=++dep;
    son[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa)continue;
        dfs(v,u);
        son[u]+=son[v];
    }
}

void build_failtree(){
    for(int i=1;i<pos;i++) addedge(fail[i],i);
    dfs(0,-1);
    //for(int i=0;i<pos;i++) printf("[%d]=%d
",i,tim[i]);
    build(1,pos,1);
    //update(1,pos-1,1,1);
    for(int i=0;i<pos;i++) if(flag[i])
        //printf("%d %d
",tim[i],tim[i]+son[i]-1);
        update(tim[i],tim[i]+son[i]-1,1,1);
}

int AC(char * s){
    int ans=0,p=0;
    for(int i=0;s[i];i++){
        p=next[p][s[i]-'a'];
        ans+=query(tim[p],1);
        //printf("%d %d %d
",p,tim[p],ans);
    }
    return ans;
}

int trans(char * s){
    int ans=0;
    for(int i=0;s[i];i++){
        ans=ans*10+s[i]-'0';
    }
    return ans;
}

int main(){
    int n,k;
    pos=0;newnode();
    str[0]=0;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=k;i++){
        scanf("%s",&S[str[i-1]+1]);
        str[i]=str[i-1]+strlen(&S[str[i-1]+1]);
        insert(&S[str[i-1]+1],i);
    }
    makefail();
    init();
    build_failtree();
    for(int i=1;i<=n;i++) vis[i]=1;
    //for(int i=0;i<pos;i++) printf("%d %d
",i,query(tim[i],1));
    //for(int i=0;i<pos;i++)printf("%d: %d %d %d
",i,next[i][0],next[i][1],fail[i]);

    for(int i=1;i<=n;i++){
        scanf("%s",S);
        if(S[0]=='+'){
            int tem=trans(&S[1]);
            if(!vis[tem]){
                //printf("fuck
");
                update(tim[mp[tem]],tim[mp[tem]]+son[mp[tem]]-1,1,1);
                vis[tem]=1;
            }
        }
        else if(S[0]=='-'){
            int tem=trans(&S[1]);
            //printf("****%d
",tem);
            if(vis[tem]){
                //printf("fuck %d %d
",tim[tem],tim[tem]+son[tem]-1);
                update(tim[mp[tem]],tim[mp[tem]]+son[mp[tem]]-1,-1,1);
                vis[tem]=0;
            }
        }
        else{
            printf("%d
",AC(&S[1]));
        }
    }
    return 0;
}

HDU 4117

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 300100
using namespace std;

char S[N];//     S 
int n,str[N],dp[N];//str[i]              
int pos;
int next[N][26],fail[N];

int newnode(){
    memset(next[pos],0,sizeof(next[pos]));
    fail[pos]=0;
    return pos++;
}

void insert(char * s,int id){
    int p=0,i=0;
    for(;s[i];i++){
        int k=s[i]-'a';
        p=next[p][k]?next[p][k]:next[p][k]=newnode();
    }
}

void makefail(){
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int v=next[u][i];
            if(v==0) next[u][i]=next[fail[u]][i];
            else q.push(v);
            if(v && u)fail[v]=next[fail[u]][i];
        }
    }
}

struct Tree{
    int l,r;
    int lazy;
    int MAX;
}tree[N<<2];

void build(int s,int t,int id){
    tree[id].l=s;
    tree[id].r=t;
    tree[id].MAX=tree[id].lazy=0;
    if(s!=t){
        int mid=(s+t)>>1;
        build(s,mid,id<<1);
        build(mid+1,t,id<<1|1);
    }
}

void update(int s,int t,int lazy,int id){
    //printf("%d %d %d
",s,t,id);
    if(tree[id].l==s && tree[id].r==t){
        tree[id].lazy=max(tree[id].lazy,lazy);
        tree[id].MAX=max(tree[id].MAX,lazy);
        return ;
    }
    if(tree[id].lazy!=0){
        tree[id<<1].lazy=max(tree[id<<1].lazy,tree[id].lazy);
        tree[id<<1|1].lazy=max(tree[id<<1|1].lazy,tree[id].lazy);
        tree[id<<1].MAX=max(tree[id<<1].MAX,tree[id].lazy);
        tree[id<<1|1].MAX=max(tree[id<<1|1].MAX,tree[id].lazy);
        tree[id].lazy=0;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(t<=mid) update(s,t,lazy,id<<1);
    else if(mid<s) update(s,t,lazy,id<<1|1);
    else{
        update(s,mid,lazy,id<<1);
        update(mid+1,t,lazy,id<<1|1);
    }
}

int query(int POS,int id){
    if(tree[id].l==tree[id].r){
        return tree[id].MAX;
    }
    if(tree[id].lazy!=0){
        tree[id<<1].lazy=max(tree[id<<1].lazy,tree[id].lazy);
        tree[id<<1|1].lazy=max(tree[id<<1|1].lazy,tree[id].lazy);
        tree[id<<1].MAX=max(tree[id<<1].MAX,tree[id].lazy);
        tree[id<<1|1].MAX=max(tree[id<<1|1].MAX,tree[id].lazy);
        tree[id].lazy=0;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(POS<=mid) return query(POS,id<<1);
    else return query(POS,id<<1|1);
}

struct Edge{
    int v,next;
}edge[N*2];
int head[N],cnt;
int tim[N],son[N],dep;//tim[i]    i    dfs 

void init(){
    memset(head,-1,sizeof(head));
    cnt=dep=0;
}

void addedge(int u,int v){
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

void dfs(int u,int fa){
    tim[u]=++dep;
    son[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa)continue;
        dfs(v,u);
        son[u]+=son[v];
    }
}

void build_failtree(){
    for(int i=1;i<pos;i++) addedge(fail[i],i);
    dfs(0,-1);
    build(1,pos,1);
}

void solve(){
    for(int i=1;i<=n;i++){
        if(dp[i]>0){
            int p=0,tem=0;
            for(int j=str[i-1]+1;j<=str[i];j++){
                p=next[p][S[j]-'a'];
                tem=max(tem,query(tim[p],1));
            }
            dp[i]+=tem;
            if(dp[i]>0) update(tim[p],tim[p]+son[p]-1,dp[i],1);
        }
    }
}

int main(){
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        pos=0;newnode();
        str[0]=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%s %d",&S[str[i-1]+1],&dp[i]);
            str[i]=str[i-1]+strlen(&S[str[i-1]+1]);
            if(dp[i]>0)insert(&S[str[i-1]+1],i);
        }
        makefail();
        init();
        build_failtree();
        solve();
        int ans=0;
        for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
        printf("Case #%d: %d
",t,ans);
    }
    return 0;
}

Noi 2011タヌキのタイプライター

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define N 100100
using namespace std;

char S[N];//     S 
vector<pair<int,int> >v[N];
int n,str[N],mp[N],ans[N];//str[i]              ，mp[i]   i         
int pos;
int next[N][26],fail[N],fa[N];//fa[i]  i   insert    

int newnode(){
    memset(next[pos],0,sizeof(next[pos]));
    fail[pos]=fa[pos]=0;
    return pos++;
}

void insert(char * s){
    int p=0,i=0,cou=0;
    for(;s[i];i++){
        if(s[i]=='P'){
            mp[++cou]=p;
        }
        else if(s[i]=='B'){
            p=fa[p];
        }
        else{
            int k=s[i]-'a',tem=p;
            p=next[p][k]?next[p][k]:next[p][k]=newnode();
            fa[p]=tem;
        }
    }
}

void makefail(){
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int v=next[u][i];
            if(v==0) next[u][i]=next[fail[u]][i];
            else q.push(v);
            if(v && u)fail[v]=next[fail[u]][i];
        }
    }
}

struct Tree{
    int l,r;
    int add;
    int sum;
}tree[N<<2];

void build(int s,int t,int id){
    tree[id].l=s;
    tree[id].r=t;
    tree[id].add=tree[id].sum=0;
    if(s!=t){
        int mid=(s+t)>>1;
        build(s,mid,id<<1);
        build(mid+1,t,id<<1|1);
    }
}

void update(int POS,int add,int id){
    tree[id].sum+=add;
    if(tree[id].l==tree[id].r){
        return ;
    }
    if(tree[id].add!=0){
        tree[id<<1].add+=tree[id].add;
        tree[id<<1|1].add+=tree[id].add;
        tree[id<<1].sum+=tree[id].add;
        tree[id<<1|1].sum+=tree[id].add;
        tree[id].add=0;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(POS<=mid) update(POS,add,id<<1);
    else update(POS,add,id<<1|1);
}

int query(int s,int t,int id){
    if(tree[id].l==s && tree[id].r==t){
        return tree[id].sum;
    }
    if(tree[id].add!=0){
        tree[id<<1].add+=tree[id].add;
        tree[id<<1|1].add+=tree[id].add;
        tree[id<<1].sum+=tree[id].add;
        tree[id<<1|1].sum+=tree[id].add;
        tree[id].add=0;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(t<=mid) return query(s,t,id<<1);
    else if(s>mid) return query(s,t,id<<1|1);
    else return query(s,mid,id<<1)+query(mid+1,t,id<<1|1);
}

struct Edge{
    int v,next;
}edge[N*2];
int head[N],cnt;
int tim[N],son[N],dep;//tim[i]    i    dfs 

void init(){
    memset(head,-1,sizeof(head));
    cnt=dep=0;
}

void addedge(int u,int v){
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

void dfs(int u,int fa){
    tim[u]=++dep;
    son[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa)continue;
        dfs(v,u);
        son[u]+=son[v];
    }
}

void build_failtree(){
    for(int i=1;i<pos;i++) addedge(fail[i],i);
    dfs(0,-1);
    build(1,pos,1);
}

void solve(char * s){
    int p=0,cou=0;
    for(int i=0;s[i];i++){
        if(s[i]=='P'){
            ++cou;
            for(int j=0;j<v[cou].size();j++){
                int x=v[cou][j].first;
                int y=v[cou][j].second;
                //printf("%d %d~%d
",y,tim[mp[x]],tim[mp[x]]+son[mp[x]]-1);
                ans[y]=query(tim[mp[x]],tim[mp[x]]+son[mp[x]]-1,1);
            }
        }
        else if(s[i]=='B'){
            //printf("%d~%d -1
",tim[p],tim[p]);
            update(tim[p],-1,1);
            p=fa[p];
        }
        else{
            p=next[p][s[i]-'a'];
            //printf("%d~%d +1
",tim[p],tim[p]);
            update(tim[p],1,1);
        }
    }
}

int main(){
    int m,x,y;
    scanf("%s",S);
    scanf("%d",&m);
    for(int i=0;i<N;i++) v[i].clear();
    for(int i=1;i<=m;i++){
        scanf("%d %d",&x,&y);
        v[y].push_back(make_pair(x,i));
    }
    pos=0;newnode();
    insert(S);
    makefail();
    init();
    build_failtree();
    //for(int i=0;i<pos;i++) printf("**%d %d
",i,tim[i]);
    solve(S);
    for(int i=1;i<=m;i++) printf("%d
",ans[i]);
    return 0;
}

BOJ 1602この問題は2013年の四川省試合のテーマです。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 1000100
using namespace std;

char S[N*2];//     S 
int n,str[N],type[N],mp[N];//              ，mp[i]   i         ，
int pos;
int next[N][26],fail[N];

int newnode(){
    memset(next[pos],0,sizeof(next[pos]));
    fail[pos]=0;
    return pos++;
}

void insert(char * s,int id){
    int p=0,i=0;
    for(;s[i];i++){
        int k=s[i]-'a';
        p=next[p][k]?next[p][k]:next[p][k]=newnode();
    }
    mp[id]=p;
}

void makefail(){
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int v=next[u][i];
            if(v==0) next[u][i]=next[fail[u]][i];
            else q.push(v);
            if(v && u)fail[v]=next[fail[u]][i];
        }
    }
}

struct Tree{
    int l,r;
    int add;
    int sum;
}tree[N<<2];

void build(int s,int t,int id){
    tree[id].l=s;
    tree[id].r=t;
    tree[id].add=tree[id].sum=0;
    if(s!=t){
        int mid=(s+t)>>1;
        build(s,mid,id<<1);
        build(mid+1,t,id<<1|1);
    }
}

void update(int s,int t,int add,int id){
    if(tree[id].l==s && tree[id].r==t){
        tree[id].add+=add;
        tree[id].sum+=add;
        return ;
    }
    if(tree[id].add!=0){
        tree[id<<1].add+=tree[id].add;
        tree[id<<1|1].add+=tree[id].add;
        tree[id<<1].sum+=tree[id].add;
        tree[id<<1|1].sum+=tree[id].add;
        tree[id].add=0;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(t<=mid) update(s,t,add,id<<1);
    else if(mid<s) update(s,t,add,id<<1|1);
    else{
        update(s,mid,add,id<<1);
        update(mid+1,t,add,id<<1|1);
    }
}

int query(int POS,int id){
    if(tree[id].l==tree[id].r){
        return tree[id].sum;
    }
    if(tree[id].add!=0){
        tree[id<<1].add+=tree[id].add;
        tree[id<<1|1].add+=tree[id].add;
        tree[id<<1].sum+=tree[id].add;
        tree[id<<1|1].sum+=tree[id].add;
        tree[id].add=0;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if(POS<=mid) return query(POS,id<<1);
    else return query(POS,id<<1|1);
}

struct Edge{
    int v,next;
}edge[N*2];
int head[N],cnt;
int tim[N],son[N],dep;//tim[i]    i    dfs 

void init(){
    memset(head,-1,sizeof(head));
    cnt=dep=0;
}

void addedge(int u,int v){
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

void dfs(int u,int fa){
    tim[u]=++dep;
    son[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa)continue;
        dfs(v,u);
        son[u]+=son[v];
    }
}

void build_failtree(){
    for(int i=1;i<pos;i++) addedge(fail[i],i);
    dfs(0,-1);
    build(1,pos,1);
}

void solve(){
	for(int i=1;i<=n;i++){
		if(type[i]==1){
			update(tim[mp[i]],tim[mp[i]]+son[mp[i]]-1,1,1);
		}
		else{
			int p=0;
			long long ans=0;
			for(int j=str[i-1]+1;j<=str[i];j++){
				p=next[p][S[j]-'a'];
				ans+=(long long)query(tim[p],1);
			}
			printf("%lld
",ans);
		}
	}
}

int main(){
	int t,T;
    char ss[10];
    scanf("%d",&T);
    for(t=1;t<=T;t++){
		pos=0;newnode();
		str[0]=0;
		scanf("%d %d",&n);
		memset(mp,0,sizeof(mp));
		for(int i=1;i<=n;i++){
			scanf("%s %s",ss,&S[str[i-1]+1]);
			str[i]=str[i-1]+strlen(&S[str[i-1]+1]);
			if(!strcmp(ss,"ask")) type[i]=2;
			else type[i]=1;
			if(type[i]==1) insert(&S[str[i-1]+1],i);
		}
		makefail();
		init();
		build_failtree();
		solve();
    }
    return 0;
}