hdu2222赤裸裸的DFA

赤裸裸的DFA，直接上模板了，可以交上去居然WA。仔细调了调，发现是原来自己写的模板有问题。之前写DFA模板的时候没有考虑到模式串会有重复并且还需要都统计的情况。大概改了改，能过这题了，但是代码改得挺乱，改天再整理整理吧。

/*
 * hdu2222/win.cpp
 * Created on: 2013-1-6
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MAX_PATTERN_NUM = 10010;
const int MAX_PATTERN_LEN = 55;
const int MAXQ = MAX_PATTERN_NUM * MAX_PATTERN_LEN;
const int MAX_TEXT_LEN = 1000100;
const int MAXK = 26; //字符集的大小
const char BASE = 'a';
typedef struct TrieNode {
    TrieNode* fail;
    TrieNode* next[MAXK];
    int cnt;
    TrieNode() {
        memset(next, 0, sizeof(next));
        cnt = 0;
        fail = NULL;
    }
} TrieNode;
TrieNode *que[MAXQ], *root;
//文本字符串及模式串
char msg[MAX_TEXT_LEN];
char pattern[MAX_PATTERN_LEN];
int N;//模式串的个数
int nCount;
int ans;
void TrieInsert(const char *s, int index) {
    int i = 0;
    TrieNode *ptr = root;
    while (s[i]) {
        int idx = s[i] - BASE;
        if (!ptr->next[idx]) {
            ptr->next[idx] = new TrieNode();
        }
        ptr = ptr->next[idx];
        i++;
    }
    ptr->cnt++;
}
void Build_DFA() {
    int rear = 1, front = 0, i;
    que[0] = root;
    root->fail = NULL;
    while (rear != front) {
        TrieNode *cur = que[front++];
        for (i = 0; i < MAXK; i++) {
            if (!cur->next[i]) {
                continue;
            }
            if (cur == root) {
                cur->next[i]->fail = root;
            } else {
                TrieNode *ptr = cur->fail;
                while (ptr) {
                    if (ptr->next[i]) {
                        cur->next[i]->fail = ptr->next[i];
                        if (ptr->next[i]->cnt) {
                            //cur->next[i]->cnt++;
                        }
                        break;
                    }
                    ptr = ptr->fail;
                }
                if (!ptr) {
                    cur->next[i]->fail = root;
                }
            }
            que[rear++] = cur->next[i];
        }
    }
}
void Run_DFA() {
    int i = 0;
    TrieNode *ptr = root;
    ptr = root;
    while (msg[i]) {
        int idx = msg[i] - BASE;
        while (!ptr->next[idx] && ptr != root) {
            ptr = ptr->fail;
        }
        ptr = ptr->next[idx];
        if (!ptr) {
            ptr = root;
        }
        TrieNode *tmp = ptr;
        while (tmp && tmp->cnt) {
            ans += tmp->cnt;
            tmp->cnt = 0;
            tmp = tmp->fail;
        }
        i++;
    }
}
void Init() {
    root = new TrieNode();
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf(" %s", pattern);
        TrieInsert(pattern, i);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        Init();
        Build_DFA();
        scanf(" %s", msg);
        ans = 0;
        Run_DFA();
        printf("%d\n", ans);
    }
    return 0;
}      

转载于:https://www.cnblogs.com/moonbay/archive/2013/01/06/2848207.html