HihoCoder 1877 - Approximate Matching

佚名 7年前 (2019-04-08) 随笔 979人围观抢沙发百度已收录

题目链接：http://hihocoder.com/problemset/problem/1877

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题意：

　　给定一个字符串，问有多少长度为 m 的字符串弱包含这个字符串。弱包含被定义为包含这个字符串或者包含这个字符串任意更改一位之后的字符串。

题解：

　　基本的 AC 自动机上 dp，先将所有可能匹配的串放到一个自动机里，每个节点的 dp[i] 表示匹配到当前节点的长度为 i 的字符串个数。先构建 fail 指针代表失配的走向，再构建 next 指针代表每一个节点，确定下一位的值后最终匹配到的节点。此时，只要在自动机上根据 next 指针 dp 就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,maxm=3e6+5,cut=300;	//maxn: µ¥¸ö×Ö·û´®×î³¤³¤¶È maxm: ac×Ô¶¯»ú×î¶à½ÚµãÊý
struct node{
    node *fa,*ch[26],*fail;
    int end,cnt;	//cnt: ÅÜµ½Õâ¸ö½ÚµãÉÏÊ±£¬×Ô¶¯»úÄÚÆ¥Åä³É¹¦µÄ×Ö·û´®ÊýÁ¿
    node(){
        fa=fail=NULL; end=cnt=0;
        fill(ch,ch+26,fa);
    }
    inline void set_fail(node *u){
        fail=u;
        cnt=end+(u->cnt);
    }
};
node *merge_node(node *a,node *b){
    if (!a) return b;
    if (!b) return a;
    int i;
    node *v;
    for (i=0;i<26;i++){
        v=a->ch[i]=merge_node(a->ch[i],b->ch[i]);
        if (v) v->fa=a;
    }
    a->end+=b->end;
    delete b;
    return a;
}
node *que[maxm];
struct ac_auto{
    node *root;
    int size;
    ac_auto(){
        root=new node;
        size=0;
    }
    void clear(){
        int i,l,r;
        node *u,*v;
        l=r=0;
        que[r++]=root;
        while (l<r){
            u=que[l++];
            for (i=0;i<26;i++) if (v=u->ch[i])
                que[r++]=v;
            delete u;
        }
        root=new node;
        size=0;
    }
    void add_str(char s[]){
        node *u,*v;
        int i,id;
        u=root;
        for (i=0;s[i]!='\0';i++){
			id=s[i]-'a';
            v=u->ch[id];
            if (!v){
                v=new node;
                u->ch[id]=v;
                v->fa=u;
            }
            u=v;
        }
        v->end++;
        size+=i;
    }
    void merge_ac(ac_auto &b){
    	size+=b.size;
        root=merge_node(root,b.root);
        b.root=new node;
        b.size=0;
    }
    void build_fail(){
        int i,l,r;
        node *u,*v,*w;
        l=0; r=0;
        for (i=0;i<26;i++) if (v=root->ch[i]){
            v->set_fail(root);
            que[r++]=v;
        }
        while (l<r){
            u=que[l++];
            for (i=0;i<26;i++) if (v=u->ch[i]){
                que[r++]=v;
                w=u->fail;
                while (w!=root){
                    if (w->ch[i]){
                        v->set_fail(w->ch[i]);
                        break;
                    }
                    w=w->fail;
                }
                if (w==root){
                    if (w->ch[i])
                        v->set_fail(w->ch[i]);
                    else
                        v->set_fail(root);
                }
            }
        }
    }
    ll query(char s[]){
        node *u;
        int i,id;
        ll ans;
        u=root; ans=0;
        for (i=0;s[i]!='\0';i++){
			id=s[i]-'a';
            while (u!=root){
                if (u->ch[id]){
                    u=u->ch[id];
                    break;
                }
                u=u->fail;
            }
            if (u==root){
                if (u->ch[id])
                    u=u->ch[id];
                else u=root;
            }
            ans+=u->cnt;
        }
        return ans;
    }
};
ac_auto ac[maxn];
char s[maxn];
int main(){
    int tt;
    int i,j,n,m,op;
    int siz;
    ll ans;
    scanf("%d",&tt);
    siz=0;
    while (tt--){
        scanf("%d%d",&n,&m);
        for (i=0;i<siz;i++) ac[i].clear();
        for (i=0;i<n;i++){
            scanf("%s",s);
            ac[0].add_str(s);
        }
        ac[0].build_fail();
        siz=1;
        for (i=0;i<m;i++){
            scanf("%d%s",&op,s);
            if (op==1){
				ac[siz++].add_str(s);
				while (siz>1&&ac[siz-1].size*2>ac[siz-2].size){
					ac[siz-2].merge_ac(ac[siz-1]);
					siz--;
				}
				ac[siz-1].build_fail();
            }
            else{
				ans=0;
				for (j=0;j<siz;j++) ans+=ac[j].query(s);
				printf("%lld\n",ans);
            }
        }
    }
    return 0;
}