洛谷P2292 [HNOI2004] L 语言题解

题目链接：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;
}