/* ` ` ` ` ` ``` ` .... ` ` `` ````` ` ` `..JyQQHkmHWHQgHHWXaJ-. ` ```` .-HHkMMMM@HMMMHHNH@HkWWma&-.` ` ` `..WHH@MMMMMM#MMHMMNWHmgMHMNMMHHHk..`` ` `` .dHHHMMMM@MMMMMMNKMMMMMHHmWWHHMHHHHe. ``` ` ` ` .JHMHMMMMMMMMMHHMMMNMHMHHMMHHmHMqHHWWH+ `` .HNHHHMNM#HMMHHWHHHHHHMMM@HHHHHHHHWHNHkHHh.` ` `` (WMMNWMMMMMHHHNqHMM@H@HMM@HHHM@HMHMHMHgkHHh.` ` ` ` (WHMHMHHHMHM@MHHMHHMMHHMHHMHH@MH@HHMHNWHHkgHb ` ` ` .HHMMHHHMMMHMMMMMHMNHMMMHWHHMgHHWHHH@MHHHHkHMH;`` ` .H@HMMM#HM@@MHHHHHMMMMHHHMmqkHbkHHMHMHH@MkHmHHMg.` ` .HHHMMHMHHWMHpWHqHH@MM@KWMMWbHHqMkWUkHHMM@HMHHHg[ ` ` ` N@MMH#MH0XXHHkWWHXWM@HHkXWHWWHHWWZyWHqMMMMH@NMH) ` MHHM#MMWwtOwUmR0zOCvWHHMkXWXXSWWWRZUVHHM@MMMHHH:` ` `WMMHH@MkwllOwH01?>;;;;:::<<<1z11juAQkkmsOwwXMMMHmS. ` ` ` HMMMMMSOz=1=z&zzz+++;;;;1zwXpWWUUUZOC1>+dHWZ+~ ` ` jHMHNZlztlwyWMH@OXkwI<<=OOOrtlz1+?>;>;>>>><;;;;;>????><;;;;:;;><><<<:::;;>?;;;;>1Oz1<:::::<1>><;;;;<>??! ` (zdS==??>;;;+zO=lz<;+u&zz+?=zx<;????_ ` ` 1zvzlz1+>+zlwUWWAwXwwOwXwwwwI;?1wuOI=??1_` ` ```.K__TkXpywzzz=1zIz?11zww01????z_`(,`` ` ` ` .MN/~~~7WHWkXwOwVwOltwvOOI??>??> Mx ` ` ` .###N/~~_?OUWWyXwwXwkUOv==>??>?j! ` (MNa, ` ` `` ````````` .d#HHH#N,~~~_<+zOVWkZXwO==?????11} dM@@@HmJ...```````` `` ` ` ` ` ` ... ` .&HHMMHHH##Hp_~_.~~<<<>_:~(M#HHHHHHHHHHHHHHHHHHN, `.MMMMNaga&J.+MMB11OX, .M@H@@@g@gggggggggmggg@gggggggmHHa., ` ` `.M@H@@@@@@@@@g@@8<+<:::::<_TMMB"""TMMHHH@@HHH@MMx JvvM#MMHgMHHH#C~~_~<1I.W@@g@@ggg@@gg@ggggmgggggmmmmggggHH@h. ``` jM@H@@H@MHHHHM@@MI>??+<<::_<-_.~-__..`_?7WMH@HHHHM2~<_(ZMMH@HHMM%~_..~~_(?dM@gg@@@@@g@gg@gggggggggggggg@ggg@H@N `` `(@MH@@H@MMMM@Hg@@M<<>>>>>;<+11+11<<:~~jaJ(M@@@@HH@@@HHb ~~(M@HHMNNbH.` ` `(M@@ggg@@gggggg@@@@@gg@gggg@ggg@@H@@@MM] .MMMHMHMMM@H@HHH3.0+>;<::~::::::::;<;:~~(HHH@MH@H@@@HHH@M-`_(HHHHHMM#Mkh (M@@@gg@gg@gggg@gg@@gg@gggg@@g@g@H@@@@@N. `XMHHHMMMMMHkH#~d81z;;<:::::::::~~:__(((HHH@@@@H@@@H@@@HHb`.dMMHHHMMMMHH[` ,M@@@g@ggg@g@g@gggggg@gg@gggggg@@H@@H@@ML `` `` ` ` MHMMHHbHWmH#`JHC?=z>>;<:::;:<<<<<<<<<:dH@@H@@@H@H@@H@H@N_.MHMq@MMHHMHqN.` .,M@@@g@@gg@@@@@@@@gg@@@@g@gggg@HMM@@@H@@H;` ` ` ` MMHHkWHg@@HD`M$;+=z>>><<::::::::::::~(d@H@H@H@@H@@H@@@HM[JH@Hqg@HHHHgqM) ``,MMHg@ggg@ggggg@gg@gMMg@gg@gggg@MM@@@@@@@N. ` `` .JHgHMHHH@@@@MF`WI;:>+?<>;:~~:~~~~~_(J+gHH@@H@@HH@@@@@@@H@@Nd@MmqggqbbHHqHb` `,M@@gggg@g@ggg@g@g@@@@@gg@g@@gg@MH@H@@@@@@b ` .MgH@MHH@@@@@@M% .k_:(<>+>?>;:~~_(dM@@HHMMHH@@@@@@@H@HH@H@H@HHHgqqmmqkbkqHgN.`.,M@@@gg@ggg@@ggggggHM@@ggg@@gg@M#H@@H@@@@@@[` ` ` `` .dMH@@MH@@@@@@@MMI_ (Xs++<;;::::_(+M@@@@@@HMM@H@H@@@H@@@H@@@H@@@HmqmqqkkkkqkHM; (MH@ggg@@gg@gggggggMM@@@gggg@@@MHH@@@@@@@@@N ` `.dMHMHHMM@@@@@@MMMZ<_ ~++wXHN###NMHM@@@@@@@g@@HMMH@@HH@@@@H@@@@HHkqqqqkqqqqHmM[ (MM@gggg@gggg@g@gH@M@@@@@@@@@@gMHH@HH@@@@@@gMM-` ` ` 4M@HH@H@@@HWHHHMNHMI1OwwXUUXM##H##MHHH@@@@@g@g@@@MMH@@@H@H@@@@@@@MqqqqqqHkqqqmHL`(M@@@g@gggggggg@MMM@@@@@@@@@@@gMHH@@H@@@@H@HHH] ` ` ` 4MH@Hg@@HHgHHMMMHM$(dWQQmgMNN#H#HHHHH@@@@@g@@@MMMMM@H@@H@H@@@@H@Mqqqqqqqqqqqqgb-.MM@ggg@gg@@@@@@@@@g@@@@@@@@@g@MHHH@@HHM@@@@gMb ` WMHHHHHggkQHHMM@HHZXM#N##N###HMMHHHHH@@@@@g@@@@@MHH@H@H@@@@@@H@@qqqmmmqqkqqqHN_.HHg@gggg@gggg@@@gg@g@@@@@@@@@gM#H@HH@H@@@@@@HN .M@HMqHgHHmggmHHMMHMHM#NN##M@MM##HHHHH@@@@@g@g@@@M#HM@@H@@@@@@H@mqmgHmqqkqmmHM:.dMM@@@g@g@gggHMg@@@@@gg@@@@@ggM#H@@HH@HH@@@@@M-` ` 7HMHqgmkqqqmmkpHMM@@HHMMMM#####HHHHHH@@@@@@@@@@@HHM@@@@@@@@@@HHqqgHmqqqqmqHMI_dM@@g@ggggggg@@@@@@@@@g@@g@@@@M#HH@@HM@@@@@@@M] ` ` ` ``?WgmmmqqqmqqqkbkbbbWHMNN####HHHHHH@@@@@@@@@@@@@MMM@@ggH@@@@MMqmmmqqkqqmqHM$j#H@@gggg@HH@@@g@g@@@@@@@@@@@@gMHHH@H@@@H@@@@@M-` ` ` ` ` `(MNNMMM##MH#HH#H#HHH@HH@HH@@@gg@@@@@@gHMMM@@@@MHggmqkkqqggqM#++MM@@ggggHMHM@gg@g@@@@@@@@@@@@gMHHH@HHHHH@@H@@HL TMMM#MHMHH##HHHHHHH@@@@@@@@@@g@g@@@@@M#NM@@@HHg@gqkkqkmmHHN>>MH@gggggMHMM@@gg@@@@@@@@@@@@g@MHHH@H@HHHH@@@@@N. ` ` .MMMHHMH#H#H#HHHHH@H@@@@@@@@@g@g@gg@@MNNM@@@M@ggqqqkqqqqHN>;dHM@gggM#HH@@@g@g@g@@@@@@@@ggHM#HH@HHH@H@@@@H@M[ ` ` ` dMHMMMHH###H#HHHHH@@@H@@@@ggg@@g@@@@H#NNM@H@ggHkqqqqkqmHMz;dMH@ggMHHH@@@@@@@@@@g@@@@@@@@gM#HHHHH@@HH@@@@HM@ ` .MHHMMHHH#H###HHH@H@H@@@@@@@@@@@@@@@M###NM@@@gqqkkqqqmHgMv>JMH@gM#HHH@H@@@@g@ggg@@@@@@@@@M#HHH@H@HH@@@@@@@M- ` (MMMMHHH#HHHHHHHH@@H@@@@@@g@@@@@@@@M###NNMHggmqkkkqggmHMI>JMMHMMHHH@@@@@@@gg@@@@@@@@@@@gHNHHHH@H@@H@@H@@@@p ` ` ` (MM@HHH#HHH#HHHHH@@@@@@@@@@@@@@H@HMHH###NMMgmqkkkHggqHMP>+MHHMHHH@H@@@@@@@Hg@@@g@@@@@ggHN#HH@HHHHM@@@@@@@b ` ` `` .MM@HHHH#HHHHHH@@H@@@@@@@@@@@H@@HMHHHHH#NMgmqqkqmgmmHMb>1dMH@HHH@@@H@H@@g@ggg@g@@@g@@gg##HHHHHHHHH@H@HH@H[` `.MHHHMHHH#HHH@H@@@@@@@@@@@HH@H@@MH#MMMM#MgqkkkqmmgmmM#<>dHMH@HHMHH@@H@@@@@@@g@g@@@@gg@##HMHHHMM@@@@@@@@HN.` ` .HHHHHH#HHHHM@@@H@@@@H@@@@@@H@@@HMMWkkHMMmkkkkqggmmmM#??dMHH@@@@HH@H@@@@@g@@@ggg@@@@ggMN#HMH@@@@HHH@@@@@M] ` .@HHHHHHHHHHHH@H@@@H@@@H@H@@@H@H@MNHkWMM@qkkkqqm@mqmHN??dH@H@HH@@@H@@H@@@@@@@@g@@@@@gH####HHMMM@gg@@@@@@M] `J@HHHHHHHHHH@@@@@@H@@@H@@@@H@@H@@HMHHMMMmkkqqqmmgmqmHHz+dMH@@@H@H@@H@@@@@@@@g@@@g@@@ggNN#NNNN##MMHg@@@@@@]` ` ` d@HHHHHHHHHHH@H@H@@@@@@@@H@@@@H@@@H@HHMmqqkkkqqggmqmHMI=dHMH@H@@@HHH@@H@@@@g@@gg@g@@g@NNN#NN#####M@@@@@@@b ` .H@@HHHHHHHHH@H@@@@H@@H@@H@@H@H@@H@@@HHHqqqqkkqkggqqqHMr+zMMH@H@@@@@HH@@@@@@@@@@@@ggggHNNNN######HM@H@@H@@N ` `.M@HH@H@HHH@H@@H@@@@@H@@@@H@@H@@@@@HH@MqqqkkkkqmHmqqmgMP<1WH@H@@@H@@@H@@@@@@@@@@@@g@@gHNNNN##H#HHHH@@H@@HHH[` ` ` (@@H@@HH@H@HH@H@@@@@@@@@@@@@@@@H@@@@HHMkkqkkkmqmgmqqqmMb(1dMH@@@@@HH@HH@@@@@@@@@@@@gggMNNN#HMH@@HHHH@@H@@H@N, ` ` ` W@@@@HHHHHHH@H@@@H@H@@@@@H@@@@H@@@H@@MHkqkkkkqqmgmqkqgH#(1vM@@H@@@@@H@@H@@@@@@@@gg@gggMN##HHHHMHHHHHHM@@@@HHN` ` ` .M@@@H@@HH@H@MH@@H@@@@@H@@@@@@H@@H@@@#dHqkkkkkHggmqqkqq@N~<=W@@@@@@@H@HH@H@@@@g@@@@g@@gMN##HHHHHHHHHHMH@@@@@HM|` ` J@@@@H@@H@H@H@@H@H@@H@@@@@@@@@@@@@@HM%JHkkkkkqmgqqkkqqqHM<(+dMHH@@@H@HH@H@@@@g@gg@@@gggMNN#MMMMMHHHHH@HHHHH@H@b` ` `.H@@@@HH@@HH@H@@@@@H@@@@@@@@H@@@MHHHM# JHqqkkkHmmqkqqkqmgM;_ #include using namespace std; using namespace atcoder; #define FOR(i, a, b) for (ll i = (a); i <= (b); i++) #define rep(i, n) FOR(i, 0, n - 1) #define NREP(i, n) FOR(i, 1, n) #define _GLIBCXX_DEBUG using ll = long long; using ui = uint64_t; using pii = pair; using piii = pair; using pll = pair; const ll INF = 1LL << 60; const ll inf = 1LL << 50; const long long mod = 998244353; using mint = modint998244353; vector di{1, 0, -1, 0}; vector dj{0, 1, 0, -1}; struct Edge { ll from; ll to; //ll co; }; ll op (ll a, ll b){return a+b;} ll mapping(ll f, ll x){return max(f, x);}; ll composition(ll f, ll g){return max(f, g);}; ll id(){return 0;}; ll e(){return 0;}; const ulong MASK30 = (1UL << 30) - 1; const ulong MASK31 = (1UL << 31) - 1; const ulong MOD = (1UL << 61) - 1; const ulong MASK61 = MOD; const ulong base = 1000000007; //mod 2^61-1を計算する関数 ulong CalcMod(ulong x) { ulong xu = x >> 61; ulong xd = x & MASK61; ulong res = xu + xd; if (res >= MOD) res -= MOD; return res; } //a*b mod 2^61-1を返す関数(最後にModを取る) ulong Mul(ulong a, ulong b) { if(a == 0 || b == 0)return 0; ulong au = a >> 31; ulong ad = a & MASK31; ulong bu = b >> 31; ulong bd = b & MASK31; ulong mid = ad * bu + au * bd; ulong midu = mid >> 30; ulong midd = mid & MASK30; return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd); } int main() { int M; string S; cin >> S >> M; vector pow(100001); pow[0] = 1; rep(i, 100000){ pow[i+1] = Mul(pow[i], base); } ll res = 0; rep(k, M){ string T; cin >> T; ulong hashs = 0; ulong hashr = 0; rep(i, T.size()){ hashs = Mul(hashs, base) + (S[i] - 'A' + 1); } rep(i, T.size()){ hashr = Mul(hashr, base) + (T[i] - 'A' + 1); } for(int i = T.size(); i <= S.size(); i++){ if(hashs == hashr)res++; hashs = CalcMod(hashs + MOD - Mul(pow[T.size()-1], (S[i-T.size()] - 'A' + 1))); hashs = Mul(hashs, base); hashs = CalcMod(hashs + (S[i] - 'A' + 1)); } } cout << res << endl; }