题目链接

HDU-3065

AC代码

因为没有在文本串字符超出字典树范围之后重置now节点导致一直WAWAWAWA。
要理解板子呀！

#include <cstdio>
#include <cstring>
#include <queue>using namespace std;int const NUM = 5e4 + 10;
int const LEN = 26;
int const N = 2e6 + 6;char str[1010][100];
char buf[N];
int nxt[NUM][LEN], fail[NUM], ed[NUM];
int root, L;
int cnt[NUM];int newCode() {for (int i = 0; i < LEN; i++)nxt[L][i] = -1;ed[L] = 0;return L++;
}void init() {memset(cnt, 0, sizeof(cnt));L = 0;root = newCode();
}int idx(char c) {return c - 'A';
}void insert(char *buf, int n) {int len = strlen(buf);int now = root;for (int i = 0; i < len; i++) {if (nxt[now][idx(buf[i])] == -1)nxt[now][idx(buf[i])] = newCode();now = nxt[now][idx(buf[i])];}ed[now] = n;
}void build() {fail[root] = root;queue<int> q;for (int i = 0; i < LEN; i++) {if (nxt[root][i] == -1) nxt[root][i] = root;else {fail[nxt[root][i]] = root;q.push(nxt[root][i]);}}while (!q.empty()) {int now = q.front();q.pop();for (int i = 0; i < LEN; i++) {if (nxt[now][i] == -1) nxt[now][i] = nxt[fail[now]][i];else {fail[nxt[now][i]] = nxt[fail[now]][i];q.push(nxt[now][i]);}}}
}void query(char *buf) {int len = strlen(buf);int now = root;for (int i = 0; i < len; i++) {if (buf[i] < 'A' || buf[i] > 'Z') {now = root;continue;}now = nxt[now][idx(buf[i])];int tmp = now;while (tmp != root) {if (ed[tmp] != 0)cnt[ed[tmp]] += 1;tmp = fail[tmp];}}
}void print(int len) {for (int i = 1; i <= len; i++) {if (cnt[i] != 0)printf("%s: %d\n", str[i], cnt[i]);}
}int main() {int n;while (scanf("%d", &n) != EOF) {init();for (int i = 1; i <= n; i++) {scanf("%s", str[i]);insert(str[i], i);}build();scanf("%s", buf);query(buf);print(n);}return 0;
}