UVALive 5103 / HDU 3695 Computer Virus on Planet Pandora (AC 자동 누 드)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=3695 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem & problem = 3104 (HDU 데이터 너무 물)
제목: n 개의 서로 다른 패턴 문자열 을 지정 합 니 다. 제 시 된 텍스트 문자열 에는 몇 개의 패턴 문자열 이 포함 되 어 있 습 니 다.주의 점:
4. 567917. 텍스트 문자열 의 여러 가지 똑 같은 형식 으로 다음 과 같이 표시 합 니 다. [qx], q 는 하나의 숫자 이 고 x 는 대문자 입 니 다
4. 567917. 텍스트 문자열 을 반전 시 킨 후에 패턴 문자열 을 포함 하 더 라 도 같은 패턴 문자열 은 하나만 계산 합 니 다
사고: AC 자동 동기 누 드 문제.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define ceil(x, y) (((x) + (y) - 1) / (y))

const int SIZE = 30;
const int N = 3e5 + 10;
const int M = 6e6 + 10;
const int INF = 0x7f7f7f7f;
const int MAX_WORD = 1e3 + 10;
const double EPS = 1e-9;
const int MOD = 2015;

int sz;
int ch[N][SIZE];
int f[N];
bool ed[N], vis[N];
char txt1[M], txt2[M];
char str[MAX_WORD];

int newnode() {
    memset(ch[sz], 0, sizeof(ch[sz]));
    ed[sz] = false;
    vis[sz] = false;
    f[sz] = 0;
    return sz++;
}

void init() {
    sz = 0;
    newnode();
}

void insert(char *s) {
    int u = 0;
    for (int i = 0; s[i]; i++) {
        int v = s[i] - 'A';
        if (!ch[u][v])
            ch[u][v] = newnode();
        u = ch[u][v];
    }
    ed[u] = true;
}

void getfail() {
    queue<int> q;

    for (int i = 0; i < SIZE; i++)
        if (ch[0][i])
            q.push(ch[0][i]);

    while (!q.empty()) {
        int r = q.front();
        q.pop();
        for (int i = 0; i < SIZE; i++) {
            int v = ch[r][i];
            if (v) {
                q.push(v);
                int u = f[r];
                while (u && !ch[u][i]) u = f[u];
                f[v] = ch[u][i];
            }
            else ch[r][i] = ch[f[r]][i];
        }
    }
}

int find(char *s) {
    int u = 0;
    int tot = 0;
    for (int i = 0; s[i]; i++) {
        int v = s[i] - 'A';
        u = ch[u][v];
        int t = u;
        while (t && !vis[t]) {
            if (ed[t]) {
                ed[t] = false;//       
                tot++;
            }
            vis[t] = true;//            
            t = f[t];
        }
    }
    return tot;
}

int main() {
    int t_case;
    scanf("%d", &t_case);
    for (int i_case = 1; i_case <= t_case; i_case++) {
        int n;
        scanf("%d", &n);
        init();
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            insert(str);
        }
        scanf("%s", txt2);

        int len = 0, x = strlen(txt2);
        for (int i = 0; i < x; i++) {
            if (txt2[i] >= 'A' && txt2[i] <= 'Z')
                txt1[len++] = txt2[i];
            else {
                i++;
                int num = 0;
                while (txt2[i] >= '0' && txt2[i] <= '9')
                    num = num * 10 + txt2[i++] - '0';
                for (int j = 0; j < num; j++)
                    txt1[len++] = txt2[i];
                i++;
            }
        }
        txt1[len] = '\0';
        for (int i = 0; i < len; i++)
            txt2[i] = txt1[len - i - 1];
        txt2[len] = '\0';

        getfail();
        int ans = 0;
        ans += find(txt1);
        ans += find(txt2);

        printf("%d
", ans);
    }   
    return 0;
}