#include #define REP(i, n) for(int i = 0;i < n;i++) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()) #define VRSORT(v) sort(v.rbegin(), v.rend()) #define ll long long #define pb(a) push_back(a) #define INF 1000000000 #define LINF 3e18+7 #define MOD 1000000007 using namespace std; typedef pair P; typedef pair LP; typedef pair PP; typedef pair LPP; typedef vectorvec; typedef vector mat; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;}; const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const double PI = acos(-1.0); const double EPS = 1e-10; template struct RollingHash { unsigned base1; vector hash1; vector pow1; void init(const string &s) { int n = s.size(); hash1.assign(n+1,0); pow1.assign(n+1,1); for(int i=0;i bLen) return false; //BのaLen乗を計算 unsigned ll t = 1; REP(i,aLen) t *= base1; //aとbの最初のaLen文字に関するハッシュ値を計算 unsigned ll aHash = 0, bHash = 0; REP(i,aLen) aHash = aHash * base1 + a[i]; REP(i,aLen) bHash = bHash * base1 + b[i]; //bの場所を1つずつ進めながらハッシュ値をチェック for(int i=0;i+aLen<=bLen;i++){ if(aHash == bHash) ret++;//bのi文字目からのaLen文字が一致 if(i + aLen < bLen) bHash = bHash * base1 + b[i+aLen] - b[i] * t; } return ret; } unsigned get(int l,int r) { unsigned t1 = ((hash1[r] - hash1[l] * pow1[r-l]) % mod + mod) % mod; return t1; } //ハッシュ値h1と長さh2Lenのハッシュ値h2を結合 //動作未確認 unsigned connect(unsigned h1, int h2, int h2Len) const { unsigned ret = ((h1 * pow1[h2Len] + h2) % mod + mod) % mod; return ret; } //区間[l1,r1)とハッシュテーブルがbからなる区間[l2,r2)の文字列の最長共通接頭辞の長さを求める //動作未確認 int LCP(const RollingHash &b, int l1, int r1, int l2, int r2){ int len = min(r1 - l1, r2 - l2); int low = -1; int high = len + 1; while(high - low > 1){ int mid = (low + high) / 2; if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid; else high = mid; } return low; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); string S; int M; cin >> S >> M; RollingHash rh; rh.init(S); ll ans = 0; REP(i,M){ string c; cin >> c; ans += rh.contain(c,S); } cout << ans << endl; }