#include #define REP(i,n) for (long long i=0;i<(n);i++) #define FOR(i,a,b) for (long long i=(a);i<(b);i++) #define RREP(i,n) for(long long i=n;i>=0;i--) #define RFOR(i,a,b) for(long long i=(a);i>(b);i--) #define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl #define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl #define dump(x) cerr << #x << " => " << (x) << endl #define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << ends #define SORT(c) sort((c).begin(),(c).end()) #define MIN(vec) *min_element(vec.begin(), vec.end()) #define MAX(vec) *max_element(vec.begin(), vec.end()) #define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり #define IN(n,m) (!(m.find(n) == m.end())) #define ENUM(m) for (auto itr = m.begin(); itr != m.end(); ++itr) #define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> " << itr->second << endl; } #define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin()) #define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin()) #define ROUND(N) setprecision(N) #define ROUND_PRINT(N,val) cout << fixed;cout << setprecision(N) << val << endl #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() #define INARR(h,w,x,y) (0 <= y && y < h && 0 <= x && x < w) #define EQ(a,b) (abs(a - b) < 1e-10) using namespace std; constexpr int dx[4] = {0,1,0,-1}; constexpr int dy[4] = {1,0,-1,0}; constexpr long double pi = M_PI; constexpr double EPS = 1e-10; constexpr long MOD = 1000000007; constexpr short shINF = 32767; constexpr long loINF = 2147483647; constexpr long long llINF = 9223372036854775807; typedef long long LL; typedef vector VI; typedef vector VVI; typedef vector VL; typedef vector VVL; typedef vector VS; typedef pair pr; typedef vector VB; typedef vector VP; typedef priority_queue,greater> pq; // ローリングハッシュのライブラリ template class RollingHash { private: typedef unsigned long long ULL; typedef pair PULL; int len; vector power1; vector power2; public: string S; // hashed[k] : 先頭k文字のhash値 vector hashed1; vector hashed2; // s : 検索対象の文字列 RollingHash(const string &s,ULL base1 = 10007LL,ULL base2 = 10009LL) : S(s),len(s.size()),power1(len+1,1),power2(len+1,1),hashed1(len+1,0),hashed2(len+1,0) { // O(N) for (int i = 0;i < len ;i++) { power1[i+1] = (power1[i] * base1) % mod1; power2[i+1] = (power2[i] * base2) % mod2; hashed1[i+1] = ((hashed1[i] * base1) + s[i]) % mod1; hashed2[i+1] = ((hashed2[i] * base2) + s[i]) % mod2; } } // [l,r) のハッシュ値を求める. PULL getHash(int l,int r) { // 負の数にならないようにmodを取ること. ULL p1 = ((hashed1[r]+mod1) - ((hashed1[l] * power1[r-l])%mod1))%mod1; ULL p2 = ((hashed2[r]+mod2) - ((hashed2[l] * power2[r-l])%mod2))%mod2; return make_pair(p1,p2); } // [] PULL connect(PULL h1,PULL h2,int h2len) { return make_pair(((h1.first*power1[h2len]) + h2.first)%mod1,((h1.second*power2[h2len]) + h2.second)%mod2); } // 区間[l1,r1) と bの区間[l2,r2) の最長共通接頭辞の長さを求める. O(log N) int LCP(const RollingHash &b,int l1 ,int r1 ,int l2 ,int r2 ) { int sz = min(r1 - l1,r2 - l2); int low = (-1),high = sz + 1; while (high - low > 1) { int mid = (low + high) / 2; if (getHash(l1,l1+mid) == b.getHash(l2,l2+mid)) low = mid; else high = mid; } return low; } }; typedef RollingHash<999999937LL,1000000009LL> RH; int main(void) { cin.tie(0); ios::sync_with_stdio(false); long M; string S,c; cin >> S; cin >> M; RH rhs(S); int ls = S.size(); LL cnt = 0; REP(i,M) { cin >> c; int lc = c.size(); RH rhc(c); auto hash = rhc.getHash(0,c.size()); REP(j,ls - (int)c.size() + 1) { if (hash == rhs.getHash(j,j+lc)) cnt++; } } cout << cnt << endl; }