#include
using namespace std;
#define _l (long long int)
struct node { int l; node *pr, *t[3]; node() { l = 0; pr = 0; memset(t, 0, sizeof(t)); } };
const int maxn = 1100009;
node nbuf_arr[maxn « 1], *nbuf(nbuf_arr), *srt, *scur; int n, m, f[maxn], ml[maxn]; char a[maxn];
void samIns(int w) { node *np(nbuf ++), *p; np-> l = scur-> l + 1; for (p = scur; p && !p-> t[w]; p = p-> pr) p-> t[w] = np; if (p) { node *q(p-> t[w]); if (q-> l != p-> l + 1) { node *nq(nbuf ++); memcpy(nq, q, sizeof(node)); nq-> l = p-> l + 1; np-> pr = q-> pr = nq; for (; p && p-> t[w] == q; p = p-> pr) p-> t[w] = nq; } else np-> pr = q; } else np-> pr = srt; scur = np; }
void samMatch() { int cl(0); node *p(srt); for (int i = 0; i < n; ++ i) { int w(a[i] - 48); if (p-> t[w]) { ++ cl; p = p-> t[w]; } else { for (; p && !p-> t[w]; p = p-> pr); if (p) { cl = p-> l + 1; p = p-> t[w]; } else { p = srt; cl = 0; } } ml[i + 1] = cl; } }
bool checkDP(int lm) { static int q[maxn]; int hd(0), tl(0); f[0] = 0; q[0] = 0; for (int i = 1; i <= n; ++ i) { f[i] = f[i - 1]; int p(i - lm); if (p >= 0) { while (hd < tl && f[q[tl - 1]] - q[tl - 1] < f[p] - p) – tl; q[tl ++] = p; } while (hd < tl && q[hd] < i - ml[i]) ++ hd; if (hd < tl) f[i] = max(f[i], f[q[hd]] + i - q[hd]); } return f[n] * 10 >= n * 9; }
int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif
scanf("%d%d", &m, &n);
srt = scur = nbuf ++;
srt-> l = 0;
srt-> pr = 0;
while (n --) {
scanf("%s", a);
for (char* i = a; *i; ++ i)
samIns(*i - 48);
samIns(2);
}
while (m --) {
scanf("%s", a);
n = strlen(a);
samMatch();
int l(0), r(n);
while (l < r) {
int mid((l + r + 1) >> 1);
if (checkDP(mid))
l = mid;
else
r = mid - 1;
}
printf("%d\n", l);
}
}