洛谷P2292 [HNOI2004] L 语言 题解
题意：
标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。
一段文章 \(T\) 是由若干小写字母构成。一个单词 \(W\) 也是由若干小写字母构成。一个字典 \(D\) 是若干个单词的集合。我们称一段文章 \(T\) 在某个字典 \(D\) 下是可以被理解的，是指如果文章 \(T\) 可以被分成若干部分，且每一个部分都是字典 \(D\) 中的单词。
例如字典 \(D\) 中包括单词 \(\texttt{is},\texttt{name},\texttt{what},\texttt{your}\)，则文章 \(\texttt{whatisyourname}\) 是在字典 \(D\) 下可以被理解的，因为它可以分成 \(4\) 个单词：\(\texttt{what},\texttt{is},\texttt{your},\texttt{name}\)，且每个单词都属于字典 \(D\)，而文章 \(\texttt{whatisyouname}\) 在字典 \(D\) 下不能被理解，但可以在字典 \(D'=D\cup\{\texttt{you}\}\) 下被理解。这段文章的一个前缀 \(\texttt{whatis}\)，也可以在字典 \(D\) 下被理解，而且是在字典 \(D\) 下能够被理解的最长的前缀。
给定一个字典 \(D\)，你的程序需要判断若干段文章在字典 \(D\) 下是否能够被理解。并给出其在字典 \(D\) 下能够被理解的最长前缀的位置。
- 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 20\)，\(1 \leq m \leq 50\)，\(1 \leq |s| \leq 20\)，\(1 \leq |t| \leq 2 \times 10^6\)，\(s\) 与 \(t\) 中均只含小写英文字母。
设 \(f_i\) 表示前 \(i\) 个字符是否可行，则有 \[ f_i = \bigvee\limits_{j-\max\{|s_i|\}}^{i-1} \left\{f_j \,\land\,t{[j+1,i]} \in S \right\} \] 其中 \(t[j+1,i]\) 表示文本串的 \([j+1,i]\) ，\(S\) 表示所有 \(s_i\) 构成的不可重集
注意到 \(1\le |s_i| \le 20\) ，因此我们可以建 \(\tt{AC}\) 自动机然后暴力转移。
具体地，我们把所有 \(s_i\) 都插入 \(\tt{AC}\) 自动机，
然后预处理出每个结点在 \(\text{fail}\) 树上的 \(i (i \le 20)\) 级祖先（认为儿子存在指向父亲的边）
这个信息可以压缩为一个二进制数，不妨设为 \(g_u\) 。
转移时，设当前所在的结点为 \(u\) ，同时维护 \(f_j(i-20 < j \le i)\) 的状态。
后者又可以压到一个二进制数 \(x\) 里，即 \(x\) 二进制下第 \(k(0\le k \le 20)\) 位为 \(1\) 表示 \(f_{i-k-1}=\text{True}\) 。
转移时，若 \(g_u \text{ and } x = \text{True}\) ，则 \(f_i=\text{True}\) 。这里的 \(\text{and}\) 表示二进制下按位与。
时间复杂度 \(O(20 \times \sum s_i + \sum t_i)\)
代码：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(405)
#define M (int)(2e6+15)
int n,m;
bitset<M> f;
char s[N],t[M];
struct Trie
{
int tot,trie[N][26],ed[N],dep[N],g[N],fail[N];
void insert(char *s)
{
int u=0,l=strlen(s+1);
for(int i=1; i<=l; i++)
{
int c=s[i]-'a';
if(!trie[u][c]) trie[u][c]=++tot;
u=trie[u][c];
}
ed[u]=1; dep[u]=l;
}
void build()
{
queue<int> q;
for(int i=0; i<26; i++)
if(trie[0][i]) q.push(trie[0][i]);
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=0; i<26; i++)
{
if(trie[u][i])
{
fail[trie[u][i]]=trie[fail[u]][i];
q.push(trie[u][i]);
}else trie[u][i]=trie[fail[u]][i];
}
}
for(int u=1; u<=tot; u++)
for(int i=u; i; i=fail[i])
if(ed[i] && dep[i] <= 21) g[u]|=(1ll << (dep[i]-1));
}
int solve(char *s)
{
int l=strlen(s+1),u=0,x=0;
for(int i=1; i<=l; i++)
{
u=trie[u][s[i]-'a'];
x=((x<<1) | f[i-1]) & ((1ll<<21)-1);
f[i]=(x&g[u])!=0;
}
for(int i=l; i>=1; i--) if(f[i]) return i;
return 0;
}
}tr;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i=1; i<=n; i++)
{
cin >> (s+1);
tr.insert(s);
} tr.build(); f[0]=1;
while(m--)
{
cin >> (t+1);
cout << tr.solve(t) << '\n';
}
return 0;
}
