- #include#include using namespace std;
- char s[205],
- t[10005];
- int fail[100001],
- q[100002],
- ch[100002][130],
- val[100002],
- id[505],
- vis[100002];
- int sz = 0,
- ans = 0,
- n;
- void trie(int x) {
- int u = 0,
- m = strlen(s);
- for (int i = 0; i) {
- int c = s[i];
- if (!ch[u][c]) ch[u][c] = ++sz;
- u = ch[u][c];
- }
- id[x] = u;
- val[u]++;
- }
- void makefail() {
- int head = 0,
- tail = 1;
- q[1] = 0;
- fail[0] = 0;
- while (head != tail) {
- int x = q[++head];
- if (head >= 100000) head = 0;
- for (int i = 0; i < 128; i++) {
- int c = ch[x][i];
- if (!c) {
- ch[x][i] = ch[fail[x]][i];
- continue;
- }
- q[++tail] = c;
- if (tail >= 100000) tail = 0;
- fail[c] = x == 0 ? 0 : ch[fail[x]][i];
- }
- }
- }
- void ac(int x) {
- int f = 0,
- k = 0,
- len = strlen(t);
- memset(vis, 0, sizeof(vis));
- for (int i = 0; i) {
- int u = t[i];
- k = ch[k][u];
- for (int j = k; j; j = fail[j]) {
- if (val[j]) {
- f = 1;
- vis[j] = 1;
- }
- }
- }
- if (!f) return;
- ans++;
- printf("web %d:", x);
- for (int i = 1; i <= n; i++) if (vis[id[i]]) printf(" %d", i);
- printf("\n");
- }
- int main() {
- int m;
- scanf("%d", &n);
- for (int i = 1; i <= n; i++) {
- scanf("%s", s);
- trie(i);
- }
- makefail();
- scanf("%d", &m);
- for (int i = 1; i <= m; i++) {
- scanf("%s", t);
- ac(i);
- }
- printf("total: %d\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2091288.html