T1订正记-AC自动机-从树到图

AC自动机已经足够棒了。

但是，好像有时还是要TLE的。

一般的AC自动还是比较好，如果在某些情况下还是会被卡掉，像是这个水题

考试的感觉

我看到这个题后，我清清楚楚的知道，这是个AC自动机+栈。

经过一番努力，把AC自动机打了出来，然后略加修饰，把栈补在里面。

我一复制，一粘贴，更高兴(？)了，过样例了，噫，我要A了。

但是我又随便写了一坨字符进去，然后就，不对了～～～～～～

最后也没调出来，后来我想想，好像是没恢复搜索栈顶元素。

我太菜了。

---以上都是废话---

更改的过程

我T60之后，想了一会，去查了Trie图，但是比较难受。

后来是有大神告诉我，可以用简单的办法构建部分Tire图，优化后就可以AC惹

但是我囿于万恶的板子，一直TLE。

唔啊啊啊啊！

我改了一会，建好图，信心满满，然后又……T了？

后来我又想，又问了几个大佬「没有得到满意的答复」

最后我充满疑惑的看到了我的while，好像不是那么回事

void ffind(){

    int j=;

    ACauto *p=root;

    sta[t++]=root;

    while(st[j]){

        int k=st[j]-'a';

        while(p!=root && p->s[k]==NULL) p=p->next;

        p=p->s[k];

        sta[t++]=p;

        if(p==NULL) p=root;

        ACauto *l=p;

        while(l!=root){//这个while

            if(l->len!=){

                t-=l->len;

                p=sta[t-];

                break;

            }

            l=l->next;

        }

        j++;

    }

}

我为什么要反复去找一个字符呢？

于是删掉while，改成if，AC。

额，一个while卡我6000ms。

分析一下，

我写的板子来自上面的两道题，有重复字符，互为子串的也有

而本题明确说明：N个字符串中无互相包含的

所以这句话就是没有意义的，它反复去找出现这个字符的地方，浪费了众多时间

而我们只需要找上一个字符出现之后的这一个字符就可以

所以，改成if更加正确。

void ffind(){

    int j=;

    ACauto *p=root;

    sta[t++]=root;

    while(st[j]){

        int k=st[j]-'a';

        while(p!=root && p->s[k]==NULL) p=p->next;

        p=p->s[k];

        sta[t++]=p;

        if(p==NULL) p=root;

        ACauto *l=p;

        if(l->len!=){

            t-=l->len;

            p=sta[t-];

        }

        j++;

    }

}

全代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define N 101010

 using namespace std;

 struct ACauto{

     ACauto *next,*s[];

     int len;

     char ch;

 }s[*N];int tot=;

 ACauto *newACauto(){

     tot++;

     return &s[tot-];

 }

 ACauto *root=newACauto();

 char st[N],ch[N];

 ACauto *q[];int f=,e=;

 bool empty(){

     if(f==e)return true;

     return false;

 }

 void push(ACauto *x){

     e++;

     q[e]=x;

 }

 ACauto* front(){

     f++;

     return q[f];

 }

 void add(const char *c){

     int j=;

     ACauto *i=root;

     while(c[j]){

         int k=c[j]-'a';

         if(i->s[k]==NULL) i->s[k]=newACauto();

         i=i->s[k];

         i->ch=c[j];

         j++;

     }

     i->len=j;

 }

 void build(){

     root->next=NULL;

     push(root);

     while(!empty()){

         ACauto *n=front();

         for(int i=;i<;i++){

             if(n->s[i]!=NULL){

                 if(n==root) n->s[i]->next=root;

                 else{

                     ACauto *p=n->next;

                     while(p!=NULL){

                         if(p->s[i]!=NULL){

                             n->s[i]->next=p->s[i];

 //                            n->s[i]=p;

                             break;

                         }

                         p=p->next;

                     }

                     if(p==NULL) n->s[i]->next=root;

                 }

                 push(n->s[i]);

             }

             else{

                 if(n==root)

                     n->s[i]=root;

                 else

                     n->s[i]=n->next->s[i];

             }

         }

     }

 }

 ACauto *sta[N];

 int t=;

 void pour(){

     for(int i=;i<t;i++){

         putchar(sta[i]->ch);

     }

     puts("");

 }

 void ffind(){

     int j=;

     ACauto *p=root;

     sta[t++]=root;

     while(st[j]){

         int k=st[j]-'a';

         while(p!=root && p->s[k]==NULL) p=p->next;

         p=p->s[k];

         sta[t++]=p;

         if(p==NULL) p=root;

         ACauto *l=p;

         if(l->len!=){

             //pour();//cout<<t<<" "<<l->len<<endl;

             t-=l->len;

             p=sta[t-];

         }

         j++;

     }

 }

 int _n=;

 void prerun(){

     for(int i=;i<;i++){

         root->s[i]=new ACauto();

         root->s[i]->ch='a'+i;

     }

 }

 int main(){

     prerun();

     scanf("%s",st);

     scanf("%d",&_n);

     for(int i=;i<=_n;i++){

         scanf("%s",ch);

         add(ch);

     }

     build();

     ffind();

     for(int i=;i<t;i++)putchar(sta[i]->ch);

     puts("");

     return ;

 }

>这里<

巴特西

T1订正记-AC自动机-从树到图

考试的感觉

更改的过程

最新文章

热门文章