526互联

做题纪要2

发布时间 2023-12-25 17:36:19作者: Vsinger_洛天依

P3808 【模板】AC 自动机（简单版）

AC自动机板子题，直接写。

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');}
}
using namespace IO;
class AC{
public:
    class Trie{
    public:
        int fail,vis[26],end; 
    }Tr[1000000];
    int cnt; 
    inline void clear(){
        memset(Tr,0,sizeof(Tr));
    }
    inline void ins(string s){
        int l=s.length(),q=0;
        for(int i=0;i<l;++i){
            if(!Tr[q].vis[s[i]-'a']) Tr[q].vis[s[i]-'a']=++cnt;
            q=Tr[q].vis[s[i]-'a']; 
        }
        Tr[q].end+=1;
    }
    inline void Get(){
        queue<int>Q; 
        for(int i=0;i<26;++i){
            if(Tr[0].vis[i]!=0){
                Tr[Tr[0].vis[i]].fail=0;
                Q.push(Tr[0].vis[i]);
            }
        }
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=0;i<26;++i){
                if(Tr[u].vis[i]!=0){
                    Tr[Tr[u].vis[i]].fail=Tr[Tr[u].fail].vis[i];
                    Q.push(Tr[u].vis[i]);
                }
                else
                    Tr[u].vis[i]=Tr[Tr[u].fail].vis[i];
            }
        }
    }
    inline int Ask(string s){
        int l=s.length(),q=0,ans=0;
        for(int i=0;i<l;++i){
            q=Tr[q].vis[s[i]-'a'];
            for(int t=q;t&&Tr[t].end!=-1;t=Tr[t].fail){
                ans+=Tr[t].end;
                Tr[t].end=-1;
            } 
        }
        return ans;
    }
}AC;
signed main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    string s;
        int n=read();
        AC.clear();
        for(int i=1;i<=n;++i){
            cin>>s;
            AC.ins(s);
        }
        AC.Get();cin>>s;
        write(AC.Ask(s));
        puts("");
}

P2292 [HNOI2004] L 语言

AC 自动机上 \(dp\)，思路大概就是用 \(ans\) 表示能够匹配的最大长度。

考虑 \(dp\)，对于 \(dp_{i}\) 表示文章的第 \(i\) 位能不能理解（若能理解则 \(dp_i=1\)，否则反之），若 \(\{i,i+1,i+2,\cdots,j\}\) 可以组成一个单词且 \(dp_i=1\) 则可以推出 \(dp_{j}=1\)，那么此时的 \(ans=i\)

接着卡常卡常卡常卡常卡常卡常卡常就过了

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');}
}
using namespace IO;
int maxl=0;
bool f[50][2000005];
int num;
class AC{
public:
    class Trie{
    public:
        int fail,vis[27],end; 
    }Tr[2000005];
    int cnt; 
    inline void ins(char *s){
        int l=strlen(s),q=0;
        for(int i=0;i<l;++i){
            if(!Tr[q].vis[s[i]-97]) 
                Tr[q].vis[s[i]-97]=++cnt;
            q=Tr[q].vis[s[i]-97]; 
        }
        Tr[q].end=l;
        maxl=max(maxl,l);
    }   
    inline void Get(){
        queue<int>Q; 
        for(int i=0;i<26;++i){
            if(Tr[0].vis[i]!=0){
                Tr[Tr[0].vis[i]].fail=0;
                Q.push(Tr[0].vis[i]);
            }
        }
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=0;i<26;++i){
                if(Tr[u].vis[i]!=0){
                    Tr[Tr[u].vis[i]].fail=Tr[Tr[u].fail].vis[i];
                    Q.push(Tr[u].vis[i]);
                }
                else
                    Tr[u].vis[i]=Tr[Tr[u].fail].vis[i];
            }
        }
    }
    inline void solve(char *s){
        int l=strlen(s),ans(0),p(0),q;
        f[num][0]=true;
        for(int i(0);i<l;++i){
            const int I(i+1);
            if(ans+maxl<I) break;
            q=s[i]-97;
            p=Tr[p].vis[q];
            for(int j(p);j;j=Tr[j].fail) 
                if(f[num][I-Tr[j].end]){
                    f[num][I]=true;
                    ans=I;
                    break;
                }           
        }
        // puts("");puts("");
        cout<<ans;
        // puts("");puts("");
    }
}AC;
signed main(){
    close();
    #ifndef ONLINE_JUDGE
//    freopen("233.in","r",stdin);
//    freopen("1.out","w",stdout);
    #endif
    char s[2000005];
    int n,m;
    cin>>n>>m;
    for(int i(1);i<=n;++i){
        cin>>s;
        AC.ins(s);
    }
    AC.Get();
    for(int i(1);i<=m;++i){
        cin>>s;
        AC.solve(s);
        cout<<'\n';
        num++;
    }
}

P5231 [JSOI2012] 玄武密码

这个 AC 自动机比较板，先匹配一遍然后再便利一遍就过了，不好评价感觉是比较水的 AC 自动机

#include<bits/stdc++.h>
using namespace std;
namespace Fread{const int SIZE = (1 << 18);char buf[SIZE],*S,*T;inline char getchar() {if(S==T){T = (S = buf) + fread(buf,1,SIZE,stdin); if(S==T) return '\n';} return *S++;}}
namespace Fwrite {const int SIZE = (1 << 18);char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout), S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{ ~NTR() { flush(); }}ztr;}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
    struct Reader{
        template <typename T>
        Reader&operator>>(T&x){char c=getchar();bool f=false;while (c<'0'||c>'9') { if(c == '-')f = true;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}if(f)x=-x;return *this;}
        Reader&operator>>(double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
        Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
        Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}
        Reader&operator>>(char&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}
        Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return *this;}
        Reader&operator>>(string&str){char c=getchar();str.clear();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return *this;}
        template<class _Tp>
        Reader&operator>>(vector<_Tp>&vec){for(unsigned i=0;i<vec.size();i++)cin>>vec[i];return *this;}
        template<class _Tp,class _tp>
        Reader&operator>>(pair<_Tp,_tp>&a){cin>>a.first>>a.second;return *this;}
        Reader(){}
    }cin;
    const char endl='\n';
    struct Writer{
    static const int set_precision = 6;
    typedef int mxdouble;
        template<typename T>
        Writer&operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(char c){putchar(c);return*this;}
        Writer& operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
        Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
        Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed) putchar(str[st++]);return *this;}
        template<class _Tp>
        Writer&operator<<(vector<_Tp>vec){for(unsigned i=0;i<vec.size()-1;i++)cout<<vec[i]<<" ";cout<<vec[vec.size()-1];return *this;}
        template<class _Tp,class _tp>
        Writer&operator<<(pair<_Tp,_tp>a){cout<<a.first<<" "<<a.second;return *this;}
        Writer(){}
    }cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
/* --------------- fast io --------------- */
int n,m;
char a[10000001];
class AC{
public:
    class Trie{
    public:
        int fail,vis[26],end; 
    }Tr[10000000];
    bool vis[10000000];
    int cnt,tot; 
    inline void clear(){
        memset(Tr,0,sizeof(Tr));
    }
    inline void ins(char *s){
        int l=strlen(s),q=0;
        for(int i=0;i<l;++i){
            if(!Tr[q].vis[s[i]-'A']) Tr[q].vis[s[i]-'A']=++cnt;
            q=Tr[q].vis[s[i]-'A']; 
        }
        Tr[q].end++;
    }
    inline void Get(){
        queue<int>Q; 
        for(int i=0;i<26;++i){
            if(Tr[0].vis[i]!=0){
                Tr[Tr[0].vis[i]].fail=0;
                Q.push(Tr[0].vis[i]);
            }
        }
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=0;i<26;++i){
                if(Tr[u].vis[i]!=0){
                    Tr[Tr[u].vis[i]].fail=Tr[Tr[u].fail].vis[i];
                    Q.push(Tr[u].vis[i]);
                }
                else
                    Tr[u].vis[i]=Tr[Tr[u].fail].vis[i];
            }
        }
        int p=0;
        for(int i=0;i<n;i++){
            p=Tr[p].vis[a[i]-'A'];
            for(int j=p;j&&!vis[j];j=Tr[j].fail) vis[j]=1;
        }
    }
    inline int Ask(char *s){
        // int l=strlen(s),q=0,ans=0;
        // for(int i=0;i<l;++i){
        //     q=Tr[q].vis[s[i]-'A'];
        //     for(int t=q;t&&Tr[t].end!=-1;t=Tr[t].fail){
        //         ans+=Tr[t].end;
        //         Tr[t].end=-1;
        //     } 
        // }
        // return ans;
        int len=strlen(s),p=0,res=0;
        for(int i=0;i<len;i++){
            p=Tr[p].vis[s[i]-'A'];
            if(vis[p]) res=i+1;
        }
        return res;
    }
}AC;
signed main(){
    char b[100005][105];
    cin>>n>>m>>a;
    for(int i=1;i<=m;i++){
        cin>>b[i];
        AC.ins(b[i]);
    }
    AC.Get();
    for(int i=1;i<=m;i++){
        cout<<AC.Ask(b[i])<<endl;
    }
}

P3966 [TJOI2013] 单词

这题当时找不到论文在哪里卡了好久

多模匹配,AC自动机

在存各个单词的同时把它们存入Trie树然后跑匹配就过了

#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
    #define FireIO
#endif
using namespace std;
#ifndef FireIO
    namespace Fread{const int SIZE = (1 << 18);char buf[SIZE],*S,*T;inline char getchar() {if(S==T){T = (S = buf) + fread(buf,1,SIZE,stdin); if(S==T) return '\n';} return *S++;}}
    namespace Fwrite {const int SIZE = (1 << 18);char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout), S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{ ~NTR() { flush(); }}ztr;}
    #ifdef ONLINE_JUDGE
        #define getchar Fread::getchar
        #define putchar Fwrite::putchar
    #endif
    namespace Fastio{
        struct Reader{
            template <typename T>
            Reader&operator>>(T&x){char c=getchar();bool f=false;while (c<'0'||c>'9') { if(c == '-')f = true;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}if(f)x=-x;return *this;}
            Reader&operator>>(double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
            Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
            Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}
            Reader&operator>>(char&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}
            Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return *this;}
            Reader&operator>>(string&str){char c=getchar();str.clear();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return *this;}
            template<class _Tp>
            Reader&operator>>(vector<_Tp>&vec){for(unsigned i=0;i<vec.size();i++)cin>>vec[i];return *this;}
            template<class _Tp,class _tp>
            Reader&operator>>(pair<_Tp,_tp>&a){cin>>a.first>>a.second;return *this;}
            Reader(){}
        }cin;
        const char endl='\n';
        struct Writer{
        static const int set_precision = 6;
        typedef int mxdouble;
            template<typename T>
            Writer&operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}
            Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
            Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
            Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
            Writer&operator<<(char c){putchar(c);return*this;}
            Writer& operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
            Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
            Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed) putchar(str[st++]);return *this;}
            template<class _Tp>
            Writer&operator<<(vector<_Tp>vec){for(unsigned i=0;i<vec.size()-1;i++)cout<<vec[i]<<" ";cout<<vec[vec.size()-1];return *this;}
            template<class _Tp,class _tp>
            Writer&operator<<(pair<_Tp,_tp>a){cout<<a.first<<" "<<a.second;return *this;}
            Writer(){}
        }cout;
    }
    #define cin Fastio :: cin
    #define cout Fastio :: cout
    #define endl Fastio :: endl
    #define max(a,b) ((a) > (b) ? (a) : (b))
    #define min(a,b) ((a) < (b) ? (a) : (b))
#endif
/* --------------- fast io --------------- */
int n,m;
char a[10000001];
class AC{
public:
    class Trie{
    public:
        int fail,vis[26],end,sz; 
    }Tr[10000000];
    int Q[10000000]; 
    bool vis[10000000];
    int cnt,tot,num; 
    inline void clear(){
        memset(Tr,0,sizeof(Tr));
    }
    inline void ins(char *s){
        int l=strlen(s),q=0;
        for(int i=0;i<l;++i){
            if(!Tr[q].vis[s[i]-'a']) Tr[q].vis[s[i]-'a']=++cnt;
            q=Tr[q].vis[s[i]-'a'];
            Tr[q].sz++; 
        }
        Tr[++num].end=q;
    }
    inline void Get(){
        int head=0,tail=0;
        for(int i=0;i<26;++i){
            if(Tr[0].vis[i]!=0){
                Q[++tail]=Tr[0].vis[i];
                // Q.push(Tr[0].vis[i]);
            }
        }
        // while(!Q.empty()){
        while(head<tail){
            int u=Q[++head];
            for(int i=0;i<26;++i){
                if(Tr[u].vis[i]!=0){
                    Tr[Tr[u].vis[i]].fail=Tr[Tr[u].fail].vis[i];
                    Q[++tail]=Tr[u].vis[i];
                    // Q.push(Tr[u].vis[i]);
                }
                else
                    Tr[u].vis[i]=Tr[Tr[u].fail].vis[i];
            }
        }
        // int p=0;
        // for(int i=0;i<n;i++){
        //     p=Tr[p].vis[a[i]-'a'];
        //     for(int j=p;j&&!vis[j];j=Tr[j].fail) vis[j]=1;
        // }
    }
    inline void Ask(){
        // int l=strlen(s),q=0,ans=0;
        // for(int i=0;i<l;++i){
        //     q=Tr[q].vis[s[i]-'a'];
        //     for(int t=q;t&&Tr[t].end!=-1;t=Tr[t].fail){
        //         ans+=Tr[t].end;
        //         Tr[t].end=-1;
        //     } 
        // }
        // return ans;
        
		for(int i=cnt;i>=0;i--) 
            Tr[Tr[Q[i]].fail].sz+=Tr[Q[i]].sz;
		for(int i=1;i<=n;i++)
            cout<<Tr[Tr[i].end].sz<<endl;
    }
}AC;
signed main(){
    #ifdef FireIO
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);std::cout.tie(0);
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif

    cerr<<"RE"<<endl;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        AC.ins(a);
    }
    AC.Get();
    AC.Ask();
}

P3167 [CQOI2014] 通配符匹配

之前写过直接A了，忘了。

P2536 [AHOI2005] 病毒检测

和上一题是双倍经验

放一下这题代码

#include<bits/stdc++.h>
using namespace std;
namespace Fread{const int SIZE = (1 << 18);char buf[SIZE],*S,*T;inline char getchar() {if(S==T){T = (S = buf) + fread(buf,1,SIZE,stdin); if(S==T) return '\n';} return *S++;}}
namespace Fwrite {const int SIZE = (1 << 18);char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout), S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{ ~NTR() { flush(); }}ztr;}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
    struct Reader{
        template <typename T>
        Reader&operator>>(T&x){char c=getchar();bool f=false;while (c<'0'||c>'9') { if(c == '-')f = true;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}if(f)x=-x;return *this;}
        Reader&operator>>(double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
        Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
        Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}
        Reader&operator>>(char&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}
        Reader&operator>>(char*st){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')st[len++]=c,c=getchar();st[len]='\0';return *this;}
        Reader&operator>>(string&st){char c=getchar();st.clear();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')st.push_back(c),c=getchar();return *this;}
        template<class _Tp>
        Reader&operator>>(vector<_Tp>&vec){for(unsigned i=0;i<vec.size();i++)cin>>vec[i];return *this;}
        template<class _Tp,class _tp>
        Reader&operator>>(pair<_Tp,_tp>&a){cin>>a.first>>a.second;return *this;}
        Reader(){}
    }cin;
    const char endl='\n';
    struct Writer{
    static const int set_precision = 6;
    typedef int mxdouble;
        template<typename T>
        Writer&operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(char c){putchar(c);return*this;}
        Writer& operator<<(char*st){int cur=0;while(st[cur])putchar(st[cur++]);return *this;}
        Writer&operator<<(const char*st){int cur=0;while(st[cur])putchar(st[cur++]);return *this;}
        Writer&operator<<(string st){int str=0,ed=st.size();while(str<ed) putchar(st[str++]);return *this;}
        template<class _Tp>
        Writer&operator<<(vector<_Tp>vec){for(unsigned i=0;i<vec.size()-1;i++)cout<<vec[i]<<" ";cout<<vec[vec.size()-1];return *this;}
        template<class _Tp,class _tp>
        Writer&operator<<(pair<_Tp,_tp>a){cout<<a.first<<" "<<a.second;return *this;}
        Writer(){}
    }cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
#define int long long
using namespace std;
int n,m,k,qwq=0,Hash[50000],cnt,ans;
unsigned long long h1[100000],h2[1005],t[1005],b=13331;
string s,cr;
bool f[500][1000];
signed main(){
	cin>>s;
	s=' '+s+'?';
	n=s.size()-1;
	t[0]=1;
	for(int i=1;i<1000;i++)
        t[i]=t[i-1]*b;
	for(int i=1;i<=n;i++){
		h1[i]=h1[i-1]*b+s[i];
		if(s[i]=='*'||s[i]=='?')
            Hash[++cnt]=i;
	}
    cin>>k;
	while(k--){
		memset(f,0,sizeof(f));
		cin>>cr;
		cr=' '+cr+'A';
		m=cr.size()-1;
		for(int i=1;i<=m;i++)
            h2[i]=h2[i-1]*b+cr[i];
		f[0][0]=1;
		for(int i=0;i<=cnt;i++){
			if(s[Hash[i]]=='*')
                for(int j=1;j<=m;j++)
                    if(f[i][j-1])
                        f[i][j]=1;
			for(int j=0;j<=m;j++){
				if(!f[i][j])
                    continue;
				int l=Hash[i]+1,r=Hash[i+1]-1,ls=j+1,rs=j+(r-l+1);
				if(h1[r]-h1[l-1]*t[r-l+1]==h2[rs]-h2[ls-1]*t[rs-ls+1])
					f[i+1][rs+(s[Hash[i+1]]=='?')]=1;
			}
		}
        qwq+=(f[cnt][m]?0:1);
	}
    cout<<qwq<<endl;
}

P3979 遥远的国度

树剖换根板子题，之前写过然后因为getchar的原因WA了一晚上

#include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
#define INF 0X66CCFF0712
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM],R,root=1,N,M;
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat,mindat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        t[lC].mindat=INF;
        t[rC].mindat=INF;
        if(l==r){
            t[q].mindat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].mindat=std::min(t[lC].mindat,t[rC].mindat);
    }
    void lazy(int q){
        t[lC].lazy=t[q].lazy;
        t[lC].mindat=t[q].lazy;
        t[rC].lazy=t[q].lazy;
        t[rC].mindat=t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].mindat=t[q].lazy=v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].mindat=std::min(t[lC].mindat,t[rC].mindat);
    }
    inline int Askmin(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return INF;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].mindat;
        if(t[q].lazy!=0)
            lazy(q);
        return std::min(Askmin(lC,l,r),Askmin(rC,l,r)); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline int lca(int u,int v){
        while(T[u].top!=T[v].top) {
            if(T[T[u].top].dep > T[T[v].top].dep)  u=T[T[u].top].fa;
            else  v=T[T[v].top].fa;
        }
        return T[u].dep>T[v].dep?v:u;
    }
    inline int Get(int x,int y){ 
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep < T[T[y].top].dep) std::swap(x,y);
            if(T[T[x].top].fa == y) return T[x].top;
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return T[x].son;
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn,T[y].dfn,val);
    }
    inline int AskTree(int x){
        if(x==root){
                #ifdef debug
                return 0X66CCFF;
                #endif
            return ST::t[1].mindat;
        }
        else if(T[x].dfn>T[root].dfn || T[x].dfn+T[x].siz-1<T[root].dfn){
                #ifdef debug
                return 0X66CCFF;//marked
                #endif
            return ST::Askmin(1,T[x].dfn,T[x].dfn+T[x].siz-1);
        } 
        else{
            int ch=Get(x,root);    
            if(T[ch].dfn+T[ch].siz-1==N)
                return ST::Askmin(1,1,T[ch].dfn-1);
            else return std::min(ST::Askmin(1,1,T[ch].dfn-1),ST::Askmin(1,T[ch].dfn+T[ch].siz,N));
        }
    }
    inline void EXchange(int x){
        root=x; 
    }
}
// inline int read(){
//     int n;
//     std::cin>>n;
//     return n;
// }
signed main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    N=read(),M=read();
    for(int i=2;i<=N;i++){
        int u=read(),v=read();
        Grape::add(u,v);
        Grape::add(v,u);
    }
    for(int i=1;i<=N;i++) a[i]=read();
    root=read();
    T[root].dep=1;
    killTree::Dfs1(root);
    killTree::Dfs2(root,root);
    ST::build(1,1,N);
    for(register int i=1;i<=M;i++){
        char q;
        std::cin>>q;
        if(q=='2'){
            int x=read(),y=read();
            killTree::TreeAdd(x,y,read());
        }
        else if(q=='1'){
            killTree::EXchange(read());
        }
        else if(q=='3'){
            std::cout<<killTree::AskTree(read())<<std::endl;
        }
    }
}

P3121 [USACO15FEB] Censoring G

栈+AC自动机，用两个栈存到哪里一个存合法字符，发现不合法就直接pop，最后倒序输出合法字符的栈就行

#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
namespace Fread{const int SIZE = (1 << 18);char buf[SIZE],*S,*T;inline char getchar() {if(S==T){T = (S = buf) + fread(buf,1,SIZE,stdin); if(S==T) return '\n';} return *S++;}}
namespace Fwrite {const int SIZE = (1 << 18);char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout), S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{ ~NTR() { flush(); }}ztr;}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
    struct Reader{
        template <typename T>
        Reader&operator>>(T&x){char c=getchar();bool f=false;while (c<'0'||c>'9') { if(c == '-')f = true;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}if(f)x=-x;return *this;}
        Reader&operator>>(double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
        Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
        Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}
        Reader&operator>>(char&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}
        Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return *this;}
        Reader&operator>>(string&str){char c=getchar();str.clear();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return *this;}
        template<class _Tp>
        Reader&operator>>(vector<_Tp>&vec){for(unsigned i=0;i<vec.size();i++)cin>>vec[i];return *this;}
        template<class _Tp,class _tp>
        Reader&operator>>(pair<_Tp,_tp>&a){cin>>a.first>>a.second;return *this;}
        Reader(){}
    }cin;
    const char endl='\n';
    struct Writer{
    static const int set_precision = 6;
    typedef int mxdouble;
        template<typename T>
        Writer&operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(char c){putchar(c);return*this;}
        Writer& operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
        Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
        Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed) putchar(str[st++]);return *this;}
        template<class _Tp>
        Writer&operator<<(vector<_Tp>vec){for(unsigned i=0;i<vec.size()-1;i++)cout<<vec[i]<<" ";cout<<vec[vec.size()-1];return *this;}
        template<class _Tp,class _tp>
        Writer&operator<<(pair<_Tp,_tp>a){cout<<a.first<<" "<<a.second;return *this;}
        Writer(){}
    }cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
#endif
/* --------------- fast io --------------- */
int n,m;
stack<int> sta,ck;
char a[10000001],b[1000005];
class AC{
public:
    class Trie{
    public:
        int fail,vis[26],end; 
    }Tr[10000000];
    bool vis[10000000];
    int cnt,tot; 
    inline void clear(){
        memset(Tr,0,sizeof(Tr));
    }
    inline void ins(char *s){
        int l=strlen(s),q=0;
        for(int i=0;i<l;++i){
            if(!Tr[q].vis[s[i]-'a']) Tr[q].vis[s[i]-'a']=++cnt;
            q=Tr[q].vis[s[i]-'a']; 
        }
        Tr[q].end=l;
    }
    inline void Get(){
        queue<int>Q; 
        for(int i=0;i<26;++i){
            if(Tr[0].vis[i]!=0){
                Tr[Tr[0].vis[i]].fail=0;
                Q.push(Tr[0].vis[i]);
            }
        }
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=0;i<26;++i){
                if(Tr[u].vis[i]!=0){
                    Tr[Tr[u].vis[i]].fail=Tr[Tr[u].fail].vis[i];
                    Q.push(Tr[u].vis[i]);
                }
                else
                    Tr[u].vis[i]=Tr[Tr[u].fail].vis[i];
            }
        }
    }
    inline void Ask(char *s){
        // int l=strlen(s),q=0,ans=0;
        // for(int i=0;i<l;++i){
        //     q=Tr[q].vis[s[i]-'A'];
        //     for(int t=q;t&&Tr[t].end!=-1;t=Tr[t].fail){
        //         ans+=Tr[t].end;
        //         Tr[t].end=-1;
        //     } 
        // }
        // return ans;
        int q=0,len=strlen(s),i=0;
        while(i<len){
            int x=s[i]-'a';
            q=Tr[q].vis[x];
            ck.push(q);
            sta.push(i);
            // cout<<q<<" "<<i<<endl;
            if(Tr[q].end){
                for(int i=1;i<=Tr[q].end;i++){
                    sta.pop();
                    ck.pop();
                }
                if(sta.empty()) q=0;
                else q=ck.top();
            }
            i++;
        }
        // int len=strlen(s),p=0,res=0;
        // for(int i=0;i<len;i++){
        //     p=Tr[p].vis[s[i]-'A'];
        //     if(vis[p]) res=i+1;
        // }
        // return res;
    }
}AC;
signed main(){
    // freopen("1.in","r",stdin);
    // freopen("1.txt","w",stdout);
    // cerr<<"RE"<<endl;
    cin>>a>>n;
    for(int i=1;i<=n;i++){
        cin>>b;
        AC.ins(b);
    }
    AC.Get();
    // for(int i=1;i<=m;i++){
    //     cout<<AC.Ask(b[i])<<endl;
    // }
    string qwq;
    AC.Ask(a);
    while(!sta.empty()){
        qwq=qwq+a[sta.top()];
        sta.pop();
    }
    for(int i=qwq.size()-1;i>=0;i--){
        cout<<qwq[i];
    }
}

P3796 【模板】AC 自动机（加强版）

板子题，不做评价。

#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
namespace Fread{const int SIZE = (1 << 18);char buf[SIZE],*S,*T;inline char getchar() {if(S==T){T = (S = buf) + fread(buf,1,SIZE,stdin); if(S==T) return '\n';} return *S++;}}
namespace Fwrite {const int SIZE = (1 << 18);char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout), S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{ ~NTR() { flush(); }}ztr;}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
    struct Reader{
        template <typename T>
        Reader&operator>>(T&x){char c=getchar();bool f=false;while (c<'0'||c>'9') { if(c == '-')f = true;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}if(f)x=-x;return *this;}
        Reader&operator>>(double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
        Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
        Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}
        Reader&operator>>(char&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}
        Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return *this;}
        Reader&operator>>(string&str){char c=getchar();str.clear();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return *this;}
        template<class _Tp>
        Reader&operator>>(vector<_Tp>&vec){for(unsigned i=0;i<vec.size();i++)cin>>vec[i];return *this;}
        template<class _Tp,class _tp>
        Reader&operator>>(pair<_Tp,_tp>&a){cin>>a.first>>a.second;return *this;}
        Reader(){}
    }cin;
    const char endl='\n';
    struct Writer{
    static const int set_precision = 6;
    typedef int mxdouble;
        template<typename T>
        Writer&operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
        Writer&operator<<(char c){putchar(c);return*this;}
        Writer& operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
        Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
        Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed) putchar(str[st++]);return *this;}
        template<class _Tp>
        Writer&operator<<(vector<_Tp>vec){for(unsigned i=0;i<vec.size()-1;i++)cout<<vec[i]<<" ";cout<<vec[vec.size()-1];return *this;}
        template<class _Tp,class _tp>
        Writer&operator<<(pair<_Tp,_tp>a){cout<<a.first<<" "<<a.second;return *this;}
        Writer(){}
    }cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
#endif
/* --------------- fast io --------------- */
int n,m;
char a[1000001],b[150][75];
class AC{
public:
    class Trie{
    public:
        int fail,vis[26],end; 
    }Tr[12000];
    int cnt,tot,num,val[12000],f[12000]; 
    inline void clear(){
        memset(Tr,0,sizeof(Tr));
        memset(f,0,sizeof(f));
        memset(val,0,sizeof(val));
        cnt=tot=num=0;
    }
    inline void ins(char *s){
        int l=strlen(s),q=0;
        for(int i=0;i<l;++i){
            if(!Tr[q].vis[s[i]-'a']) Tr[q].vis[s[i]-'a']=++cnt;
            q=Tr[q].vis[s[i]-'a']; 
        }
        Tr[q].end=++num;
    }
    inline void Get(){
        queue<int>Q; 
        for(int i=0;i<26;++i)
            if(Tr[0].vis[i]!=0)
                Q.push(Tr[0].vis[i]);
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=0;i<26;++i){
                if(Tr[u].vis[i]){
                    Tr[Tr[u].vis[i]].fail=Tr[Tr[u].fail].vis[i];
                    Q.push(Tr[u].vis[i]);
                }
                else
                    Tr[u].vis[i]=Tr[Tr[u].fail].vis[i];
            }
        }
    }
    inline int Ask(char *s){
        int l=strlen(s),q=0,ans=0;
        for(int i=0;i<l;++i){
            q=Tr[q].vis[s[i]-'a'];
            for(int t=q;t;t=Tr[t].fail)
                val[t]++;
        }
        for(int i=0;i<=cnt;++i)
            if(Tr[i].end)
                ans=max(ans,val[i]),
                f[Tr[i].end]=val[i];
        return ans;
        // int q=0,len=strlen(s),i=0;
        // while(i<len){
        //     int x=s[i]-'a';
        //     q=Tr[q].vis[x];
        //     ck.push(q);
        //     sta.push(i);
        //     // cout<<q<<" "<<i<<endl;
        //     if(Tr[q].end){
        //         for(int i=1;i<=Tr[q].end;i++){
        //             sta.pop();
        //             ck.pop();
        //         }
        //         if(sta.empty()) q=0;
        //         else q=ck.top();
        //     }
        //     i++;
        // }
    }
}AC;
signed main(){
    // freopen("1.in","r",stdin);
    // freopen("1.txt","w",stdout);
    // cerr<<"RE"<<endl;
    while(1){
        cin>>n;
        if(n==0) return 0;
        AC.clear();
        for(int i=1;i<=n;i++){
            cin>>b[i];
            AC.ins(b[i]);
        }
        cin>>a;
        AC.Get();
        int x=AC.Ask(a);
        // for(int i=1;i<=m;i++){
        //     cout<<AC.Ask(b[i])<<endl;
        // }
        cout<<x<<endl;
        for(int i=1;i<=n;i++)
            if(AC.f[i]==x)
                cout<<b[i]<<endl;
    }
}

Dominating Patterns

双倍经验，和上面一样