TLE on #8 #9 #18 #26

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,ubuf[1<<23],*u=ubuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename TP> inline TP read(TP &num)
{
	TP x=0;
	int f=0;
	char ch=getchar();
	while(ch<48||ch>57) f|=ch=='-',ch=getchar();
	while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return num=f?-x:x;
}
template<typename ...Args> inline void read(Args &...args)
{
	(read(args),...);
}
template<typename TP> inline void write(TP x)
{
	(x<0)?(putchar('-'),x=-x):0;
	(x>9)?(write(x/10),0):0;
	putchar((x%10)^48);
}
template<typename TP> inline void writeln(TP x)
{
	write<TP>(x);
	puts("");
}
inline void read_string(string &s)
{
	char ch=getchar();
	while(ch==' '||ch=='\n'||ch=='\r') ch=getchar();
	while(ch!=' '&&ch!='\n'&&ch!='\r') s+=ch,ch=getchar();
}
#define base 10169
mt19937 rnd(time(0));
int n;
string s[200003],t;
unsigned long long ha[200003],val[2000003],pw[2000003];
set<int> len[500001];
__gnu_pbds::gp_hash_table<unsigned long long,int> mp,mp1;
inline unsigned long long get_hash(int l,int r)
{
	return val[r]-(l?val[l-1]*pw[r-l+1]:0);
}
inline int cvt(string s)
{
    if(s.size()<4) return 0;
    int x=s[s.size()-1]-'a',y=s[s.size()-2]-'a',z=s[s.size()-3]-'a',__4=s[s.size()-4]-'a';
    return x*26*26*26+y*26*26+z*26+__4;
}
inline int cvt(char xx,char yy,char zz,char _4)
{
    if(!yy||!zz||!_4) return 0;
    int x=xx-'a',y=yy-'a',z=zz-'a',__4=_4-'a';
    return x*26*26*26+y*26*26+z*26+__4;
}
signed main()
{
	pw[0]=1;
	rep(i,1,200002) pw[i]=pw[i-1]*base;
	read(n);
	rep(i,1,n)
	{
		read_string(s[i]);
		for(auto j:s[i]) ha[i]=(ha[i]*base+j);
        mp1[ha[i]]=1;
		len[cvt(s[i])].emplace(s[i].size());
	}
	rep(i,0,500000) len[i].emplace(1),len[i].emplace(2),len[i].emplace(3);
	read_string(t);
	rep(i,0,t.size()-1)
	{
		if(!i) val[i]=t[i];
		else val[i]=(val[i-1]*base+t[i]);
		for(auto lens:len[cvt(t[i],i==0?0:t[i-1],i<=1?0:t[i-2],i<=2?0:t[i-3])])
		{
			if(lens>i+1) break;
			unsigned long long h=get_hash(i-lens+1,i);
			if(mp1.find(h)!=mp1.end()) ++mp[h];
		}
	}
	rep(i,1,n) writeln(mp[ha[i]]);
	return 0;
}