题面

Sol

先建立AC自动机，trie树上每个字符串结束的位置记录下它的长度\(len\)

设\(f[i]\)表示前\(i\)个字符是否被翻译

在AC自动机上匹配，跳\(fail\)转移，该点为\(x\)，则\(f[i]\)由\(f[i-len[x]]\)转移而来

太菜了不会trie的暴力

# include 
    
     # define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(4e6 + 10);IL ll Read(){    RG ll x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}int n, m, tot, ch[26][23333], ed[23333], fail[23333];bool f[_];char s[30], t[_];queue 
     
       Q;IL void Insert(){    RG int len = strlen(s), x = 0;    for(RG int i = 0; i < len; ++i){        if(!ch[s[i] - 'a'][x]) ch[s[i] - 'a'][x] = ++tot;        x = ch[s[i] - 'a'][x];    }    ed[x] = len;}IL void Get_Fail(){    for(RG int i = 0; i < 26; ++i) if(ch[i][0]) Q.push(ch[i][0]);    while(!Q.empty()){        RG int fa = Q.front(); Q.pop();        for(RG int i = 0; i < 26; ++i)            if(!ch[i][fa]) ch[i][fa] = ch[i][fail[fa]];            else fail[ch[i][fa]] = ch[i][fail[fa]], Q.push(ch[i][fa]);    }}IL int Compare(){    Fill(f, 0); f[0] = 1; RG int ans = 0, len = strlen(t + 1);    for(RG int i = 1, x = 0; i <= len; ++i){        x = ch[t[i] - 'a'][x];        for(RG int j = x; j; j = fail[j]){            f[i] |= f[i - ed[j]];            if(f[i]) break;        }    }    for(RG int i = 1; i <= len; ++i) if(f[i]) ans = i;    return ans;}int main(RG int argc, RG char* argv[]){    n = Read(); m = Read();    for(RG int i = 1; i <= n; ++i) scanf(" %s", s), Insert();    Get_Fail();    for(RG int i = 1; i <= m; ++i) scanf(" %s", t + 1), printf("%d\n", Compare());    return 0;}