例如字典$D$中包括单词 is , your , what , name ，则文章 whatisyourname 是在字典$D$下可以被理解的，因为它可以分成 4 个单词： what , is , your , name ，且每个单词都属于字典$D$，而文章 whatisyouname 在字典$D$下不能被理解，但可以在字典 D’=D+D’=D+you 下被理解。这段文章的一个前缀 whatis ，也可以在字典$D$下被理解，而且是在字典$D$下能够被理解的最长的前缀。
char s[1000005]; int n, m, tr[10005][30], tag[10005], tot, len; bool ok[1000005];
inlinevoidinsert(char *str, int l){ int now = 0; for (int i = 1; i <= l; i++) { if (!tr[now][str[i]-'a']) tr[now][str[i]-'a'] = ++tot; now = tr[now][str[i]-'a']; } tag[now] = 1; }
inlinevoidquery(char *str, int st, int l){ int now = 0; for (int i = st; i <= l; i++) { if (!tr[now][str[i]-'a']) break; now = tr[now][str[i]-'a']; if (tag[now]) ok[i] = 1; } }
intmain(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", s+1); len = strlen(s+1); insert(s, len); } for (int i = 1; i <= m; i++) { memset(ok, 0, sizeof(ok)); ok[0] = 1; scanf("%s", s+1); len = strlen(s+1); for (int j = 1; j <= len; j++) { if (ok[j-1]) query(s, j, len); } for (int j = len; j >= 0; j--) { if (ok[j]) { printf("%d\n", j); break; } } } return0; }
