【 총 결 】 AC 자동 처리 조회 (bzo 3881 Divljak + bzoj 2780 Sevenk Love Oimaster + bzoj 2754 야옹 별의 출석)

AC 자동 동기
AC 자동 동 기 는 다 중 템 플 릿 일치 문 제 를 해결 하 는 알고리즘 입 니 다.
그것 의 장점 은 사고방식 이 이해 하기 쉽 고 코드 가 간결 하여 선형 시간 내 에 해답 을 구 할 수 있다 는 데 있다.단점 은 모든 템 플 릿 을 먼저 알 아야 한 다 는 것 이다. 실제 운용 에서 조회 해 야 할 템 플 릿 문자열 을 미리 알 수 없 는 경우 가 많다.
AC 자동 동기 와 관련 된 문 제 는 뚜렷 한 특징 이 있다. 텍스트 문자열 이 비교적 길 거나 텍스트 문자열 이 유일 / 비교적 적 고 다 중 모드 문자열 이 일치 하 며 오프라인 이 가능 하 며 패턴 문자열 의 총 길 이 는 일정한 제한 이 있다.문 제 를 처리 할 때 도 먼저 오프라인 으로 모든 패턴 문자열 의 AC 자동 동 기 를 만들어 야 한다.
AC 자동 동기 상 결합 트 리 (fail 트 리) 및 dp (일치 방안 / 확률) 고찰.이 총 결 은 주로 fail 트 리 에 관 한 조작 을 쓴다.
일치 하 는 문제
문자열 이 일치 하 는 조 회 는 다음 과 같은 몇 가지 기본 형식 이 있 습 니 다.
텍스트 문자열 일치

단일 텍스트 문자열 에 있 는 모든 패턴 문자열 이 나타 나 는 횟수 를 조회 합 니 다 (같은 패턴 문자열 이 여러 번 나타 나 면 여러 번 계산 합 니 다)

AC 자동 동기 의 모든 결점 구조 에 대해 e n d end 배열, e n d i endi endi 는 결점 i i 로 끝 나 는 패턴 문자열 개 수 를 표시 합 니 다.b f s bfs bfs 구조 f a i l fail fail 체인 시 e n d end end end 를 이용 하여 s u m sum sum 배열, s u m i sum 를 처리 할 수 있 습 니 다.i sumi 는 결점 i i i 가 f a i l fail fail 트 리 에서 루트 노드 경로 에 있 는 모든 점 의 e n d end end 의 합 을 나타 낸다.
텍스트 문자열 이 결점 i i i 에 일치 할 때 답 에 s u m i sumi sumi 면 됩 니 다.복잡 도 는 O (8739 ° S * 8739 ° C + 8739 ° T * 8739 ° C) O (| S | + | T |) O (8739 ° S * 8739 ° C + 8739 ° T * 8739 ° C) 8739 ° S * 8739 ° S * 8739 ° S * 8739 ° 는 텍스트 꼬치 길이 이 고 8739 ° T * 8739 ° T | 8739 ° T * 8739 ° C 는 모델 꼬치 길이 입 니 다.

단일 텍스트 문자열 에 나타 난 패턴 문자열 의 개 수 를 조회 합 니 다.

먼저 f a i l fail fail 트 리 의 d f s dfs dfs 순 서 를 처리 합 니 다.
1. 한 점 에 일치 할 때마다 답 에 s u m sum sum 을 추가 하 는 것 을 고려 합 니 다. 그 중에서 일부 점 은 여러 번 중복 계산 되 고 무 거 운 부분 은 점 에서 루트 경로 까지 의 공동 경로 입 니 다.따라서 일치 하 는 과정 에서 도착 한 모든 결점 을 꺼 내 고 d f s dfs dfs 순서 로 정렬 하 며 각 점 의 s u m sum sum 을 더 하여 인접 한 두 점 의 L C A LCA LCA 의 s u m sum sum 을 뺀 다.복잡 도가 정렬 된 l o g log 가 많아 졌 습 니 다.

한 그룹의 텍스트 문자열 (여러 개) 에 나타 난 패턴 문자열 의 개 수 를 조회 합 니 다 (같은 패턴 문자열 은 이 텍스트 문자열 에 여러 번 계산 합 니 다)

같은 2. 그러나 지금 은 텍스트 문자열 의 일치 가 끝 난 후에 결점 을 꺼 내 정렬 처리 합 니 다.
패턴 문자열 일치

모든 패턴 문자열 이 여러 텍스트 문자열 에 나타 나 는 횟수 를 조회 합 니 다 (한 텍스트 문자열 에 여러 번 나타 나 는 계산)

우선 모든 모드 문자열 을 AC 자동 동 기 를 만 들 고 각 문자열 에 대응 하 는 끝 점 p o s pos pos pos 를 기록 합 니 다.f a i l fail fail 트 리 의 d f s dfs dfs 순서 와 각 노드 의 하위 트 리 크기 s z sz sz 를 처리 합 니 다.
각각 AC 자동 동기 에 텍스트 문자열 을 삽입 하고 하나의 노드 에 일치 할 때마다 값 v a l val 을 1 로 추가 합 니 다.한 꼬치 의 출현 횟수 는 f a i l fail fail 트 리 의 하위 트 리 결점 v a l val 의 합 을 발견 할 수 있 습 니 다.
모든 아이디어 트 리 는 d f s dfs dfs 순서 에서 반드시 연속 적 인 부분 이 고 답 구간 의 구 화 를 고려 하여 구조 BIT 를 고려 하여 l o g log 노드 개수 의 시간 에 구 해 낼 수 있 습 니 다.복잡 도 O (8739 ° S * 8739 ° S * 8739 ° T * 8739 °) l o g * 8739 ° T * 8739 ° T * 8739 ° O (| S | + | T |) log | T |) O (8739 ° S * 8739 ° + 8739 ° T * 8739 °) log * 8739 ° T * 8739 °)

모든 패턴 문자열 이 여러 텍스트 문자열 에 나타 난 횟수 를 각각 조회 합 니 다 (한 텍스트 문자열 에 여러 번 계산 합 니 다)

각각 텍스트 문자열 을 삽입 합 니 다. 일치 하 는 노드 를 꺼 내 고 d f s dfs dfs 순서 로 정렬 합 니 다. 인접 한 두 점 L C A LCA LCA 의 v a l val 에서 1 을 줄 입 니 다.복잡 도 는 역시 l o g log 의 것 이다.

모든 패턴 문자열 이 여러 그룹의 텍스트 문자열 에 나타 난 횟수 를 조회 합 니 다 (한 그룹의 텍스트 문자열 에 여러 번 계산 합 니 다)

같은 2. 그러나 지금 은 텍스트 문자열 의 일치 가 끝 난 후에 결점 을 꺼 내 정렬 처리 합 니 다.
아래 세 문 제 는 상기 조회 의 간단 한 응용 이다.
bzoj3881:[Coci2015]Divljak
패턴 문자열 일치 2.

#include
using namespace std;
const int N=2e6+10;

int n,qr,df[N],top[N],f[N],sz[N],son[N],d[N];
int bit[N],pos[100010],dfn,pr;
int head[N],to[N<<1],nxt[N<<1],tot;

char s[N],SS[70];
queue<int>Q;

char cp;
inline void rd(int &x)
{
	cp=getchar();x=0;
	for(;!isdigit(cp);cp=getchar());
	for(;isdigit(cp);cp=getchar()) x=(x<<3)+(x<<1)+(cp^48);
}

inline void ot(int x)
{
	int re=0;
	for(;x;x/=10) SS[++re]='0'+x%10;
	if(!re) putchar('0');
	for(;re;--re) putchar(SS[re]);
}

inline void lk(int u,int v)
{to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}

inline bool cmp(const int&A,const int&B){return df[A]<df[B];}

void dfs(int x)
{
	int i,j;sz[x]=1;son[x]=-1;
	for(i=head[x];i;i=nxt[i]){
		j=to[i];if(j==f[x]) continue;
		d[j]=d[x]+1;dfs(j);sz[x]+=sz[j];
		if((son[x]==-1) || sz[j]>sz[son[x]]) son[x]=j;
	}
}

void dfss(int x,int tpo)
{
	df[x]=++dfn;top[x]=tpo;
	if(son[x]==-1) return;
	dfss(son[x],tpo);
	for(int j,i=head[x];i;i=nxt[i]){
		j=to[i];if(j==f[x] || j==son[x]) continue;
		dfss(j,j);
	}
}

inline int LCA(int x,int y)
{
    for(;top[x]!=top[y];x=f[top[x]]) 
      if(top[x]==0 || d[f[top[x]]]<d[f[top[y]]]) swap(x,y);
    if(d[x]<d[y]) swap(x,y);
	return y;
}

inline void modify(int x,int vv)
{for(;x<=dfn;x+=(x&(-x))) bit[x]+=vv;}

inline int query(int x)
{
	int re=0;
	for(;x;x-=(x&(-x))) 
	  re+=bit[x];
	return re;
}

inline void upp(int x)
{
	for(;~x;x=f[top[x]]){
		modify(df[top[x]],pr);
		if(df[x]<dfn) modify(df[x]+1,-pr);
	}
}

struct AC{
	queue<int>Q;
	int vs[N],cot,len,ch[N][26],cnt;
	
	inline void ins(int id,char *s)
	{
		int i,j,alp,u=0;len=strlen(s);
		for(i=0;i<len;++i){
			alp=s[i]-'a';
			if(!ch[u][alp]) ch[u][alp]=++cnt;
			u=ch[u][alp];
		}
		pos[id]=u;
	}
	
	void getfail()
	{
		int i,j,x,y,z,u;
		for(i=0;i<26;++i){
			x=ch[0][i];if(x) Q.push(x);
		}
		for(;!Q.empty();){
			x=Q.front();Q.pop();y=f[x];
			lk(x,y);lk(y,x);
			for(i=0;i<26;++i){
				z=ch[x][i];u=ch[y][i];
				if(!z) {ch[x][i]=u;continue;}
				f[z]=u;Q.push(z);
			}
		}
	}
	
	inline void ad(char *s)
    {
	   int i,j,alp,u=0,x;cot=0;len=strlen(s);
	   for(i=0;i<len;++i){
	      u=ch[u][s[i]-'a'];
	      vs[++cot]=u;
	   }
	   sort(vs+1,vs+cot+1,cmp);
	   cot=unique(vs+1,vs+cot+1)-vs-1;
	   pr=1;upp(vs[1]);
	   for(i=2;i<=cot;++i){
	   	 pr=1;upp(vs[i]);pr=-1;
			upp(LCA(vs[i-1],vs[i]));
	   }
    }
}ac;

int main(){
	int i,j,op,x;
	rd(n);f[0]=-1;
	for(i=1;i<=n;++i){scanf("%s",s);ac.ins(i,s);}
	ac.getfail();d[0]=1;dfs(0);dfss(0,0);
	rd(qr);
	for(;qr;--qr){
		rd(op);
		if(op==1){
			scanf("%s",s);ac.ad(s);
		}else{
			rd(x);
			ot(query(df[pos[x]]));putchar('
');
		}
	}
	return 0;
}

bzoj2780[Spoj]8093 Sevenk Love Oimaster
패턴 문자열 일치 2.

#include
using namespace std;
const int N=360010;

int n,qr,df[N],top[N],f[N],sz[N],son[N],d[N];
int bit[N],pos[60010],dfn;
int head[N],to[N<<1],nxt[N<<1],tot;

char t[N],SS[70];
string s[10010];

char cp;
inline void rd(int &x)
{
	cp=getchar();x=0;
	for(;!isdigit(cp);cp=getchar());
	for(;isdigit(cp);cp=getchar()) x=(x<<3)+(x<<1)+(cp^48);
}

inline void ot(int x)
{
	int re=0;
	for(;x;x/=10) SS[++re]='0'+x%10;
	if(!re) putchar('0');
	for(;re;--re) putchar(SS[re]);
}

inline void lk(int u,int v)
{to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}

inline bool cmp(const int&A,const int&B){return df[A]<df[B];}

void dfs(int x)
{
	int i,j;sz[x]=1;son[x]=-1;
	for(i=head[x];i;i=nxt[i]){
		j=to[i];if(j==f[x]) continue;
		d[j]=d[x]+1;dfs(j);sz[x]+=sz[j];
		if((son[x]==-1) || sz[j]>sz[son[x]]) son[x]=j;
	}
}

void dfss(int x,int tpo)
{
	df[x]=++dfn;top[x]=tpo;
	if(son[x]==-1) return;
	dfss(son[x],tpo);
	for(int j,i=head[x];i;i=nxt[i]){
		j=to[i];if(j==f[x] || j==son[x]) continue;
		dfss(j,j);
	}
}

inline int LCA(int x,int y)
{
    for(;top[x]!=top[y];x=f[top[x]]) 
      if(top[x]==0 || d[f[top[x]]]<d[f[top[y]]]) swap(x,y);
    if(d[x]<d[y]) swap(x,y);
	return y;
}

inline void modify(int x,int vv)
{for(;x<=dfn;x+=(x&(-x))) bit[x]+=vv;}

inline int query(int x)
{
	int re=0;
	for(;x;x-=(x&(-x))) 
	  re+=bit[x];
	return re;
}

struct AC{
	queue<int>Q;
	int vs[N],cot,len,ch[N][26],cnt;
	
	inline void ins(int id,char *s)
	{
		int i,j,alp,u=0;len=strlen(s);
		for(i=0;i<len;++i){
			alp=s[i]-'a';
			if(!ch[u][alp]) ch[u][alp]=++cnt;
			u=ch[u][alp];
		}
		pos[id]=u;
	}
	
	void getfail()
	{
		int i,j,x,y,z,u;
		for(i=0;i<26;++i){
			x=ch[0][i];if(x) Q.push(x);
		}
		for(;!Q.empty();){
			x=Q.front();Q.pop();y=f[x];
			lk(x,y);lk(y,x);
			for(i=0;i<26;++i){
				z=ch[x][i];u=ch[y][i];
				if(!z) {ch[x][i]=u;continue;}
				f[z]=u;Q.push(z);
			}
		}
	}
	
	inline void ad(string s)
    {
	   int i,j,alp,u=0,x;cot=0;
	   len=s.size();
	   for(i=0;i<len;++i){
	      u=ch[u][s[i]-'a'];
	      if(u) vs[++cot]=u;
	   }
	   if(!cot) return;
	   sort(vs+1,vs+cot+1,cmp);
	   cot=unique(vs+1,vs+cot+1)-vs-1;
	   modify(df[vs[1]],1);
	   for(i=2;i<=cot;++i){
	   	 modify(df[vs[i]],1);
		 modify(df[LCA(vs[i-1],vs[i])],-1);
	   }
    }
}ac;

int main(){
	int i,j,op,x;
	rd(n);rd(qr);
	for(i=1;i<=n;++i) cin>>s[i];
	for(i=1;i<=qr;++i){scanf("%s",t);ac.ins(i,t);}
	ac.getfail();
	d[0]=1;f[0]=-1;dfs(0);dfss(0,0);
	for(i=1;i<=n;++i) ac.ad(s[i]);
	for(i=1;i<=qr;++i){
		x=pos[i];
		ot((query(df[x]+sz[x]-1)-query(df[x]-1)));
		putchar('
');
	}
	return 0;
}

고양이 별의 출석 체크
패턴 문자열 일치 3. + 텍스트 문자열 일치 3.

#include
#define itr map::iterator
#define fi first
#define sc second
using namespace std;
const int N=1e5+10;

int n,m,df[N],top[N],f[N],sz[N],son[N],d[N];
int bit[N],pos[N],ans[50005],dfn,nwss;
int ed[N],sum[N];
int head[N],to[N<<1],nxt[N<<1],tot;

vector<int>nam[50005][2];

char cp,SS[70];
inline int rd()
{
	cp=getchar();int x=0;
	for(;!isdigit(cp);cp=getchar());
	for(;isdigit(cp);cp=getchar()) x=(x<<3)+(x<<1)+(cp^48);
    return x;
}

inline void ot(int x)
{
	int re=0;
	for(;x;x/=10) SS[++re]='0'+x%10;
	if(!re) putchar('0');
	for(;re;--re) putchar(SS[re]);
}

inline void lk(int u,int v)
{to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}

inline bool cmp(const int&A,const int&B){return df[A]<df[B];}

void dfs(int x)
{
	int i,j;sz[x]=1;son[x]=-1;
	for(i=head[x];i;i=nxt[i]){
		j=to[i];if(j==f[x]) continue;
		d[j]=d[x]+1;sum[j]=sum[x]+ed[j];dfs(j);sz[x]+=sz[j];
		if((son[x]==-1) || sz[j]>sz[son[x]]) son[x]=j;
	}
}

void dfss(int x,int tpo)
{
	df[x]=++dfn;top[x]=tpo;
	if(son[x]==-1) return;
	dfss(son[x],tpo);
	for(int j,i=head[x];i;i=nxt[i]){
		j=to[i];if(j==f[x] || j==son[x]) continue;
		dfss(j,j);
	}
}

inline int LCA(int x,int y)
{
    for(;top[x]!=top[y];x=f[top[x]]) 
      if(top[x]==0 || d[f[top[x]]]<d[f[top[y]]]) swap(x,y);
    if(d[x]<d[y]) swap(x,y);
	return y;
}

inline void modify(int x,int vv)
{for(;x<=dfn;x+=(x&(-x))) bit[x]+=vv;}

inline int query(int x)
{
	int re=0;
	for(;x;x-=(x&(-x))) re+=bit[x];
	return re;
}

struct AC{
	queue<int>Q;
	map<int,int>ch[N];
	int vs[N<<1],cot,len,cnt;
	
	inline void ins(int id)
	{
		int alp,u=0;
		for(len=rd();len;--len){
			alp=rd();
			if(!ch[u][alp]) ch[u][alp]=++cnt,u=cnt;
			else u=ch[u][alp];
		}
		ed[u]++;pos[id]=u;
	}
	
	void getfail()
	{
		int x,y,z,v,u;itr i;
		for(i=ch[0].begin();i!=ch[0].end();++i) Q.push(i->sc);
		for(;!Q.empty();){
			x=Q.front();Q.pop();y=f[x];
			lk(x,y);lk(y,x);
			for(i=ch[x].begin();i!=ch[x].end();++i){
				for(u=i->fi,z=y;z && (!ch[z][u]);z=f[z]);
                v=ch[z][u];f[i->sc]=v;Q.push(i->sc);
			}
		}
	}
	
	inline void cal(int id)
    {
	   int i,j,alp,u=0,z;nwss=cot=0;
	   for(j=0;j<2;++j){
	   	  u=0;
	   	  for(len=nam[id][j].size(),i=0;i<len;++i){
	   	     alp=nam[id][j][i];
	   	     if(!ch[u][alp]){
	   	   	    for(z=f[u];z && (!ch[z][alp]);z=f[z]);
	   	   	    u=ch[z][alp];
	   	     }else u=ch[u][alp];
	   	     if(u) vs[++cot]=u;
	     }
	   }
	   if(!cot) return;
	   sort(vs+1,vs+cot+1,cmp);
	   cot=unique(vs+1,vs+cot+1)-vs-1;
	   modify(df[vs[1]],1);nwss+=sum[vs[1]];
	   for(i=2;i<=cot;++i){
	   	 z=LCA(vs[i-1],vs[i]);
		 nwss-=sum[z];nwss+=sum[vs[i]];
	   	 modify(df[vs[i]],1);modify(df[z],-1);
	   }
	   ans[id]=nwss;
    }
}ac;

int main(){
	int i,j,x;
	n=rd();m=rd();
    for(i=1;i<=n;++i)
    	for(j=0;j<2;++j)
    		for(x=rd();x;--x)
    			nam[i][j].push_back(rd());
    for(i=1;i<=m;++i) ac.ins(i);
    ac.getfail();
	d[0]=1;f[0]=-1;dfs(0);dfss(0,0);
    for(f[0]=0,i=1;i<=n;++i) ac.cal(i);
	for(i=1;i<=m;++i){
		x=pos[i];
		ot(query(df[x]+sz[x]-1)-query(df[x]-1));
		putchar('
');
	}
    for(i=1;i<=n;++i) 
	 ot(ans[i]),putchar(i==n?'
':' ');
	return 0;
}