1 #include<bits/stdc++.h> 2 using namespace std; 3 #define M(a, b) memset(a, b, sizeof(a)); 4 const int maxn = 1000 + 10; 5 6 struct AhoCorasickAutomata { 7 int ch[maxn][26], val[maxn], last[maxn], f[maxn], sz; 8 9 int idx(char s) { return s - 'a'; } 10 11 void init() { 12 sz = 0; 13 M(ch, 0); M(val, 0); M(last, 0); 14 } 15 16 void insert(char* s, int v) { 17 int u = 0, len = strlen(s); 18 for (int i = 0; i < len; ++i) { 19 int c = idx(s[i]); 20 if (!ch[u][c]) { 21 ch[u][c] = ++sz; 22 val[sz] = 0; 23 M(ch[sz], 0); 24 } 25 u = ch[u][c]; 26 } 27 val[u] = v; 28 } 29 30 void getFail() { 31 queue<int> q; 32 f[0] = 0; 33 for (int c = 0; c < 26; ++c) { 34 int u = ch[0][c]; 35 if (u) { f[u] = 0; q.push(u); last[u] = 0; } 36 } 37 while(!q.empty()) { 38 int r = q.front(); q.pop(); 39 for (int c = 0; c < 26; ++c) { 40 int u = ch[r][c]; 41 if (!u) { ch[r][c] = ch[f[r]][c]; continue; } 42 q.push(u); 43 int v = f[r]; 44 while(v && !ch[v][c]) v = f[v]; //找到失配的第一个结点 45 f[u] = ch[v][c]; 46 last[u] = val[f[u]] ? f[u] : last[f[u]]; 47 } 48 } 49 } 50 51 void print(int j) { 52 if (j) { 53 printf("%d: %d ", j, val[j]); 54 print(last[j]); 55 } 56 } 57 58 void find(char* T) { 59 int len = strlen(T); 60 int j = 0; 61 for (int i = 0; i < len; ++i) { 62 int c = idx(T[i]); 63 j = ch[j][c]; 64 if (val[j]) print(j); 65 else if (last[j]) print(last[j]); 66 } 67 } 68 69 }; 70 71 AhoCorasickAutomata ac; 72 73 int main() { 74 int n, m, v; 75 char s[maxn]; 76 while(~scanf("%d%d", &n, &m)) { 77 ac.init(); 78 while(n--) { 79 scanf("%s %d", s, &v); 80 ac.insert(s, v); 81 } 82 ac.getFail(); 83 while(m--) { 84 scanf("%s", s); 85 ac.find(s); 86 } 87 } 88 89 return 0; 90 }