https://www.luogu.com.cn/discuss/417158

#include<bits/stdc++.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f3f
#define INF 0x7f7f7f7f7f
using namespace std;
namespace Iwara{
	template<class T> T MAX(T x,T y){
		return x>y?x:y;
	}
	template<class T,class ... Arg> T MAX(T x,T y,Arg ... arg){
		return MAX(x>y?x:y,arg...);
	}
	template<class T> T MIN(T x,T y){
		return x<y?x:y;
	}
	template<class T,class ... Arg> T MIN(T x,T y,Arg ... arg){
		return MIN(x<y?x:y,arg...);
	}
	template<class T> T lowbit(T x){
		return x&-x;
	}
	template<class T> void SWAP(T &x,T &y){
		T qwq;
		qwq=x;
		x=y;
		y=qwq;
		return;
	}
}
using namespace Iwara;
const ll MAXN=1e5+5;
char ch[MAXN];
ll n,m,ans,l;
char q[MAXN];
ll maxl[MAXN],maxr[MAXN];
ll pre[MAXN],suf[MAXN];
int main(){
	cin>>(ch+1);
	n=strlen(ch+1);
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>(q+1);
		l=strlen(q+1);
		ll lpos=0,rpos=l+1;
		for(int j=0;j<=n+1;j++)maxl[j]=0,maxr[j]=l+1;
		for(int j=1;j<=l;j++)pre[j]=0,suf[j]=l+1;
		ll nowp=0;
		for(int j=2;j<=l;j++){
			while(nowp&&q[nowp+1]!=q[j])nowp=pre[nowp];
			if(q[nowp+1]==q[j])pre[j]=++nowp;
		}
		nowp=l+1;
		for(int j=l-1;j>=1;j--){
			while(nowp<=l&&q[nowp-1]!=q[j])nowp=suf[nowp];
			if(q[nowp-1]==q[j])suf[j]=--nowp;
		}
		for(ll L=1,R=n;L<=n;L++,R--){
			while(lpos&&q[lpos+1]!=ch[L])lpos=pre[lpos];
			if(q[lpos+1]==ch[L])lpos++;
			while(rpos<=l&&q[rpos-1]!=ch[R])rpos=suf[rpos];
			if(q[rpos-1]==ch[R])rpos--;
			maxl[L]=MAX(maxl[L-1],lpos);
			maxr[R]=MIN(maxr[R+1],rpos);
		}
		for(int j=1;j<=n;j++){
			if(maxl[j]+1>=maxr[j+1]||maxr[j]-1<=maxl[j-1]){
				ans++;
				break;
			}
		}
	}
	cout<<ans;
	return 0;
}