HDU3065

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
char s[1005][55];
char str[2000005];

struct AC_Automaton
{
    int ch[50005][26], fail[50005], id[50005];
    int tot;

    void init(){
        tot = 0;
        memset(ch, -1, sizeof(ch));
        memset(fail, 0, sizeof(fail));
        memset(id, 0, sizeof(id));
    }

    void insert(char *ss, int cnt){
        int p = 0, len = strlen(ss);
        for (int i = 0; i < len; i++){
            if(ch[p][ss[i] - 'A'] == -1){
                ch[p][ss[i] - 'A'] = ++tot;
            }
            p = ch[p][ss[i] - 'A'];
        }
        id[p] = cnt;
    }

    void build(){
        int l = 0, r = 0, q[50005];
        for (int i = 0; i < 26; i++){
            if(ch[0][i] == -1){
                ch[0][i] = 0;
            }else{
                q[r++] = ch[0][i];
            }
        }
        while(l < r){
            int p = q[l++];
            for (int i = 0; i < 26; i++){
                if(ch[p][i] == -1){
                    ch[p][i] = ch[fail[p]][i];
                }else{
                    fail[ch[p][i]] = ch[fail[p]][i];
                    q[r++] = ch[p][i];
                }
            }
        }
    }

    void count(char *ss){
        int p = 0, ans[1005];
        int len = strlen(ss);
        memset(ans, 0, sizeof(ans));
        //memset(vis, 0, sizeof(vis));
        for (int i = 0; i < len; i++){
            if(ss[i] < 'A' || ss[i] > 'Z'){
                p = 0;
                continue;
            }
            p = ch[p][ss[i] - 'A'];
            int temp = p;
            while(temp && id[temp]){
                ans[id[temp]]++;
                temp = fail[temp];
            }
        }
        for (int i = 1; i <= n; i++){
            if(ans[i] != 0){
                printf("%s: %d\n", s[i], ans[i]);
            }
        }
    }

}AC;

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    while(scanf("%d", &n) == 1){
        AC.init();
        for (int i = 1; i <= n; i++){
            scanf("%s", s[i]);
            AC.insert(s[i], i);
        }
        AC.build();
        scanf("%s", str);
        AC.count(str);
    }

    return 0;
}
/**/

测一下这种数组:

2
AA
AAA
ooxxCC%dAAAoen....ENDooxxCC%dAAAoen....ENDooxxCC%dAAAoen....ENDooxxCC%dAAAoen....END

AA: 8

AAA: 4

２
ABA
AAA
diasifsAojfsdBAdfinasAA

没有输出