[HNOI2004] L语言

Description

给定一个由 n 个字符串 s 组成的字典，再给定 m 句话 t ，求每句话在该字典下可以理解的最长前缀。
$n\leq 20,m\leq 50,|s|\leq 10,|t|\leq 2\times 10^6$

Solution

考虑朴素做法。设 f[i] 表示 t[1:i] 能否被理解。

$f[i]= \bigcup\limits_{j<i} (f[j] \text{ and } [t[i:j] \text{in} \{s\}])$

如果采用哈希判断，复杂度为 $\mathcal{O}(m|s||t|)$ ，有点卡常。

题目中 $|s|\leq 10$ 的范围很有特点，这意味着每次向前至多只会比较 10 次。
抛开哈希，我们重新考虑匹配的过程。对 s 串建 AC 自动机，当匹配 t[i] 时，假设在 AC 自动机上走到了 u 节点。若 u 有 end 标记，我们就再回到 t 串查询对应的 f[j] 是否为 true ；否则，我们就遍历 fail[u] ，直到找到一个两者均为 true 的位置或者找到根节点。在这个过程中，我们只需要 fj 以及 u 在 fail 树上的所有祖先的 end 标记信息。由于 fail 树树高不超过 10 ，所以两者我们都可以状压。即令 $las=2^i\times[f_{j-i}]$ ，$g_u=g_{\text{fa}_u}+(2^{\text{len}_u}\times [\text{end}[u]])$ 。

于是就可以做到 $\mathcal{O}(1)$ 判断了。复杂度 $\mathcal{O}(m|t|)$ 。

本质就是通过状压卡常数而已 😶。10 只是方便了一个 int 可以压下来，任意长度都可以状压。

但是如果哈希就无法卡常了... 所以说将匹配过程看作在 fail 树上跳，由于树是可以预处理出来的，并且树上算法还是挺成熟的，没准可以有奇效。

Code

const int N=1e3+5,L=2e6+5;
using namespace std;
int n,m;
namespace ACM{
    int tot;
    int g[N],dep[N],fail[N],endpos[N],t[N][26];
    void insert(char *s){
        int len=strlen(s),u=0;
        for(int i=0;i<len;++i){
            int v=s[i]-'a';
            if(!t[u][v]) t[u][v]=++tot,dep[tot]=dep[u]+1;
            u=t[u][v]; 
        }
        endpos[u]=1;
    }
    void prework(){
        queue<int>q;int u=0;
        for(int i=0;i<26;++i)
            if(t[u][i]) q.push(t[u][i]),g[t[u][i]]=endpos[t[u][i]];
        while(!q.empty()){
            u=q.front();q.pop();
            for(int i=0;i<26;++i)
                if(!t[u][i]) t[u][i]=t[fail[u]][i];
                else{
                    int v=t[u][i];fail[v]=t[fail[u]][i];
                    g[v]=g[fail[v]]|(endpos[v]<<dep[v]-1);q.push(v);
                }
        }
    }
    int solve(char *s){
        int len=strlen(s),u=0,lst=1,ans=0;
        for(int i=0;i<len;++i){
            u=t[u][s[i]-'a'];
            bool now=(g[u]&lst);
            lst<<=1,lst|=now,lst&=1023;
            if(now) ans=i+1;
        }
        return ans;
    }
}
char s[N],t[L];
int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%s",s),ACM::insert(s);
    ACM::prework();
    for(int i=1;i<=m;++i)
        scanf("%s",t),printf("%d\n",ACM::solve(t));
    return 0;
}