#include #include using namespace atcoder; using mint = modint998244353; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef __int128_t lll; typedef string str; #include #include namespace mp = boost::multiprecision; using Bint = mp::cpp_int; // 多倍長整数 using Real = mp::number>; #define MOD (998244353LL) #define INF (2147483647/3) #define INFS (-2147483647/3) #define LLINF (9223372036854775807LL/3) #define LLINFS (-9223372036854775807LL/3) #define rep(i, N) for (ll i=0; i<(ll)(N); ++i) #define rrep(i, N) for (ll i=N-1; i>=0LL; --i) #define all(A) A.begin(),A.end() #define elif else if #define RET return 0 #define CIN(x) cin >> x #define COUT(x) cout << x << endl #define COUTS(x) cout << x << " " #define ENDL cout << endl #define YES cout << "Yes" << endl #define NO cout << "No" << endl #define YESRET cout << "Yes" << endl; RET #define NORET cout << "No" << endl; RET #define LL(N) ll N; cin >> N #define __INT1(A) LL(A) #define __INT2(A,B) __INT1(A);__INT1(B) #define __INT3(A,B,C) __INT2(A,B);__INT1(C) #define __INT4(A,B,C,D) __INT3(A,B,C);__INT1(D) #define __INTSEL(_1,_2,_3,_4,_5,...) _5 #define INT(...) __INTSEL(__VA_ARGS__,__INT4,__INT3,__INT2,__INT1)(__VA_ARGS__) #define __STR1(A) str A; cin >> A #define __STR2(A,B) __STR1(A);__STR1(B) #define __STR3(A,B,C) __STR2(A,B);__STR1(C) #define __STR4(A,B,C,D) __STR3(A,B,C);__STR1(D) #define __STRSEL(_1,_2,_3,_4,_5,...) _5 #define STR(...) __STRSEL(__VA_ARGS__,__STR4,__STR3,__STR2,__STR1)(__VA_ARGS__) #define __MIN1(A) min(A,LLINF) #define __MIN2(A,B) min(__MIN1(A),B) #define __MIN3(A,B,C) min(__MIN2(A,B),C) #define __MIN4(A,B,C,D) min(__MIN3(A,B,C),D) #define __MINSEL(_1,_2,_3,_4,_5,...) _5 #define MIN(...) __MINSEL(__VA_ARGS__,__MIN4,__MIN3,__MIN2,__MIN1)(__VA_ARGS__) #define __MAX1(A) max(A,LLINFS) #define __MAX2(A,B) max(__MAX1(A),B) #define __MAX3(A,B,C) max(__MAX2(A,B),C) #define __MAX4(A,B,C,D) max(__MAX3(A,B,C),D) #define __MAXSEL(_1,_2,_3,_4,_5,...) _5 #define MAX(...) __MAXSEL(__VA_ARGS__,__MAX4,__MAX3,__MAX2,__MAX1)(__VA_ARGS__) #define PII pair #define PIS pair #define PSI pair #define PSS pair #define SLL set #define SINT SLL #define SSTR set #define SPLL set> #define SPII SPLL #define SPLS set> #define SPIS SPLS #define SPSL set> #define SPSI SPSL #define PQL priority_queue #define PQI PQL #define RPQL priority_queue, greater> #define RPQI RPQL #define VLL vector #define VINT VLL #define VSTR vector #define VVLL(A, H, W) vector A(H,VLL(W)) #define VVINT(A, H, W) VVLL(A, H, W) #define VVSTR(A, H, W) vector A(H,VSTR(W)) #define VIN(A,N) VINT A(N); rep(__VIN_i,N) cin >> A[__VIN_i] #define VST(A,N) VSTR A(N); rep(__VST_i,N) cin >> A[__VST_i] #define VIN2(A,B,N) VINT A(N); VINT B(N); rep(__VIN_i,N) cin >> A[__VIN_i] >> B[__VIN_i] #define VPII(A,N) vector A(N) #define VPIS(A,N) vector A(N) #define VPSI(A,N) vector A(N) #define VPSS(A,N) vector A(N) #define VPIIN(A,N) VPII(A,N); rep(__VPIIN_i,N) cin >> A[__VPIIN_i].first >> A[__VPIIN_i].second #define ins(a) insert(a) #define pb(a) push_back(a) #define SORT(A) sort(all(A)) #define SSORT(A) stable_sort(all(A)) #define REV(A) reverse(all(A)) #define INCR(A) rep(__INCR_i,A.size()) ++A[__INCR_i] #define DECR(A) rep(__DECR_i,A.size()) --A[__DECR_i] // N以上の最小値 #define LB(A,N) *lower_bound(all(A), N) // Nを超える最小値 #define UB(A,N) *upper_bound(all(A), N) #define DEBUG COUT("DEBUG") #define DEB(x) cout << "DEB " << x << endl // AのB乗 ll POW(ll A,ll B) { ll __POW = 1; ll __Asub = A; ll __Bsub = B; while(__Bsub > 0) { if(__Bsub & 1) __POW *= __Asub;//Bの下からi番目のbitが1ならば、A^(2^i)をかける __Asub *= __Asub; __Bsub >>= 1; } return __POW; } // AのB乗(mod998) ll MPOW(ll A,ll B) { ll __MPOW = 1; ll __Asub = A; ll __Bsub = B; while(__Bsub > 0) { if(__Bsub & 1) __MPOW = __MPOW * __Asub % MOD; __Asub = __Asub * __Asub % MOD; __Bsub >>= 1; } return __MPOW; } // 二分探索(めぐる式) // vector A:sort済み整数列(長さN) // A_i>=Kであるような最小のi // すべてK未満ならNを返す ll BinarySearch(ll N,vector A,ll K) { ll __BS_ok = N-1; ll __BS_ng = -1; if(A[N-1] < K) return N; while(__BS_ok - __BS_ng != 1) { ll __BS_now = (__BS_ok + __BS_ng) / 2; if(A[__BS_now] >= K) __BS_ok = __BS_now; else __BS_ng = __BS_now; } return __BS_ok; } // N頂点M辺のグラフが二部グラフかどうか // vector> A:辺一覧(長さM,0-indexed) bool IsBipartiteGraph(ll N,ll M,vector> A) { dsu d(N*2); rep(__IBG_i,M) { d.merge((A[__IBG_i].first),(A[__IBG_i].second)+N); d.merge((A[__IBG_i].first)+N,(A[__IBG_i].second)); } rep(__IBG_i,N) { if(d.same(__IBG_i,__IBG_i+N)) return 0; } return 1; } // ローリングハッシュ // Sが連続部分文字列としてTをもつならtrue ll rolling_hash(str S, str T){ ll RH_ans=0; #define B1 100000007 #define B2 1000000007 ll RH_SL=S.length(); ll RH_TL=T.length(); // B^mを用意する ull pow_B_m_1 = 1, pow_B_m_2 = 1; for(int RH_k = 0; RH_k < RH_TL; RH_k++){ pow_B_m_1 *= B1, pow_B_m_2 *= B2; } // sの先頭m文字のハッシュ値shと,tのハッシュ値th ull sh1 = 0, sh2 = 0, th1 = 0, th2 = 0; for(int RH_k = 0; RH_k < RH_TL; RH_k++){ th1 = th1 * B1 + T[RH_k], th2 = th2 * B2 + T[RH_k]; sh1 = sh1 * B1 + S[RH_k], sh2 = sh2 * B2 + S[RH_k]; } // sをずらしてハッシュ値を更新 for(int RH_k = 0; RH_k <= RH_SL - RH_TL; RH_k++){ // shのハッシュ==thのハッシュならtrue if(sh1 == th1 && sh2 == th2) ++RH_ans; if(RH_k < RH_SL - RH_TL){ sh1 = sh1 * B1 + S[RH_TL + RH_k] - S[RH_k] * pow_B_m_1; sh2 = sh2 * B2 + S[RH_TL + RH_k] - S[RH_k] * pow_B_m_2; } } return RH_ans; } int main() { cout << fixed << setprecision(15); STR(S); INT(M); ll ans=0; rep(i,M) { STR(C); ans+=rolling_hash(S,C); } COUT(ans); }