洛谷 P2292. L 语言
原题链接
简单
作者:
清风qwq
,
2023-06-04 18:25:13
,
所有人可见
,
阅读 118
#include <bits/stdc++.h>
using namespace std;
const int N = 2000010, M = 410, P = (1 << 19) - 1;
int n, m;
int tr[M][30], tot;
int ne[M], l[M], g[N];
char str[N];
bool End[M], f[N];
void insert() {
int p = 0, len = strlen(str);
for (int i = 0; i < len; i ++ ) {
int c = str[i] - 'a';
if (!tr[p][c]) tr[p][c] = ++ tot;
p = tr[p][c];
}
End[p] = true;
}
void build() {
queue<int> q;
for (int i = 0; i < 26; i ++ )
if (tr[0][i])
q.push(tr[0][i]);
while (q.size()) {
int t = q.front();
g[t] = g[ne[t]] | (End[t] ? (1 << l[t]) : 0);
q.pop();
for (int i = 0; i < 26; i ++ ) {
int np = tr[t][i];
if (!np) tr[t][i] = tr[ne[t]][i];
else {
l[np] = l[t] + 1;
ne[np] = tr[ne[t]][i];
q.push(np);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
scanf("%s", str);
insert();
}
build();
while (m -- ) {
scanf("%s", str + 1);
int len = strlen(str + 1);
int x = 1, res = 0;
for (int i = 1, p = 0; i <= len; i ++ ) {
int c = str[i] - 'a';
p = tr[p][c];
if (g[p] & x) f[i] = 1, res= i;
else f[i] = 0;
x = (x * 2 + f[i]) & P;
}
printf("%d\n", res);
}
return 0;
}