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("");
}
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++;
}
}
这个 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;
}
}
这题当时找不到论文在哪里卡了好久
多模匹配,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();
}
之前写过直接A了，忘了。
和上一题是双倍经验
放一下这题代码
#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;
}
树剖换根板子题，之前写过然后因为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];
}
}
板子题，不做评价。
#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;
}
}
双倍经验，和上面一样
标签：return,int,char,while,&&,纪要,getchar From： https://www.cnblogs.com/LuoTianYi66ccff/p/17926598.html