HDU3695(AC自动机模板题)

时间：2022-06-04 00:48:46

　　题意：给你n个字符串，再给你一个大的字符串A，问你着n个字符串在正的A和反的A里出现多少个？

　　其实就是AC自动机模板题啊( ╯□╰ )

　　正着query一次再反着query一次就好了

/*  gyt

       Live up to every day            */

#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<cstring>`

#include<queue>

#include<set>

#include<string>

#include<map>

#include <time.h>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = ;

const ll maxm = 1e7;

const ll mod = 1e9 + ;

const int INF = 0x3f3f3f;

const ll inf = 1e15 + ;

const db eps = 1e-;

const int kind=;

struct node{

    node *fail;

    node *next[kind];

    int coun;

    void nodee() {

        fail=NULL;

        coun=;

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

            next[i]=NULL;

    }

}*root;

char str[maxn];

char tmp[maxn];

int ans=;

void updata() {

    node *p=root;

    int len=strlen(str);

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

        int pos=str[i]-'A';

        if (p->next[pos]==NULL) {

            p->next[pos]=new node;

            p->next[pos]->nodee();

            p=p->next[pos];

        }

        else  p=p->next[pos];

    }

    p->coun++;

}

void getfail() {

    node *p=root, *son, *tmp;

    queue<struct node*>que;

    que.push(p);

    while(!que.empty()) {

        tmp=que.front();

        que.pop();

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

            son=tmp->next[i];

            if (son!=NULL) {

                if (tmp==root) {

                    son->fail=root;

                }

                else {

                    p=tmp->fail;

                    while(p) {

                        if (p->next[i]) {

                            son->fail=p->next[i];

                            break;

                        }

                        p=p->fail;

                    }

                    if (!p)  son->fail=root;

                }

                que.push(son);

            }

        }

    }

}

void query() {

    int len=strlen(str);

    node *p, *tmp;

    p=root;

    int cnt=;

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

        int pos=str[i]-'A';

        while(!p->next[pos]&& p!=root)  p=p->fail;

        p=p->next[pos];

        if (!p)  p=root;

        tmp=p;

        while(tmp!=root) {

            if (tmp->coun>=) {

                cnt+=tmp->coun;

                tmp->coun=-;

            }

            else  break;

            tmp=tmp->fail;

        }

    }

    ans+=cnt;

}

void solve() {

    ans=;

    root=new node;

    root->nodee();

    root->fail=NULL;

    int n;   scanf("%d", &n);

    getchar();

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

        gets(str);  updata();

    }

    getfail();

    gets(str);

    int len=strlen(str);

    int nn=;  char c;

    int now=;  int cnt=;

    while() {

        if (now>=len)  break;

        if (str[now]=='[') {

            now++;

            while(str[now]>=''&&str[now]<='') {

                nn = nn*+(str[now]-'');

                now++;

            }

            c=str[now];

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

                tmp[cnt++]=c;

            nn=;

            now++;

            now++;

        }

        else  {

          //  if (str[now]==']') {

           //     now++;  continue;

          //  }

            tmp[cnt++]=str[now];  now++;

        }

       // cout<<str[now]<<endl;

    }

    tmp[cnt]='\0';

    for (int i=; i<=cnt; i++)  str[i]=tmp[i];

   // cout<<str<<endl;

    query();

    reverse(str, str+strlen(str));

   // cout<<str<<endl;

    query();

    cout<<ans<<endl;

}

int main() {

    int t = ;

   // freopen("in.txt", "r", stdin);

    scanf("%d", &t);

    while(t--)

        solve();

    return ;

}

相关文章