[HNOI2004]L语言

字符串hash实现匹配

#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<cstring>
typedef unsigned long long u64;
int n,m;
char buf[1<<20|1];
#define p first
#define len second
std::vector<std::pair<u64,int>>v;
int ok[1<<20|1];
u64 hsh[1<<20|1];
u64 Exp[1<<20|1];
inline u64 gethash(int l,int r){
    return hsh[r] - hsh[l-1] * Exp[r-l+1];
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(0);
    std::cin >> n >> m;
    for(int i=1;i<=n;++i){
        std::cin >> buf;
        u64 p=0;
        for(int i=0;buf[i];++i)
            p=p*121355+buf[i]-'a';
        v.push_back(std::make_pair(p,strlen(buf)));
    }
    Exp[0]=1;
    for(int i=1;i<=100;++i)Exp[i]=Exp[i-1]*121355;
    for(int i=1;i<=m;++i){
        std::cin >> (buf+1);
        u64 p=0;
        for(int i=1;buf[i];++i)
            hsh[i]=p=p*121355+buf[i]-'a';
        int l = strlen(buf+1),ans=0;
        ok[0]=1;
        for(int i=1;i<=l;++i){
            ok[i]=0;
            for(std::pair<u64,int>&o:v){
                if(i < o.len)continue;
                if(gethash(i-o.len+1,i) == o.first)
                    ok[i] |= ok[i-o.len];
            }
            if(ok[i])ans = i;
        }
        std::cout << ans << '
';
    }
}