#include #include #include #include #include #include #include #include #include #include #define REP(i, n) for(int (i) = 0; (i) < (n); ++(i)) // RollingHashクラス class RollingHash{ private: #define rep(i, n) for(int (i) = (0); (i) < (n); ++(i)) using LLi = long long int; using V_LLi = std::vector; // 32ビット以下の 素数 static constexpr LLi One_E_Nine= 1e9; static constexpr int mod_size = 3; static std::array mod; static bool mod_not_chosen; static constexpr int base_size = 2; static constexpr std::array base{9999991, 799976819}; // 原始元 std::vector> power; // power[k][i][j] = (base[i])^k in mod[j] // ハッシュ値 | hash[range][i][j] : base[i], mod[j] 下での [0, range) の ハッシュ値 std::vector> hash; // thePrimes[i] + 1e9 において, baseは原始元 static constexpr int Arr_Size_thePrimes = 138; static constexpr std::array thePrimes{ -9971, -9707, -9167, -9149, -8939, -8793, -8769, -8577, -8559, -8537, -8531, -8331, -7901, -7463, -7421, -7361, -7241, -7217, -6917, -6363, -6329, -6267, -6183, -6167, -6113, -6053, -5603, -5297, -5027, -4623, -4433, -4379, -4251, -4181, -4007, -3887, -3851, -3753, -3741, -3641, -3593, -3329, -3323, -3311, -2951, -2763, -2433, -2423, -2411, -2361, -2327, -2321, -1919, -1817, -1757, -1661, -1379, -1337, -1317, -1097, -869, -807, -647, -609, -497, -413, -117, -107, 7, 411, 433, 637, 753, 871, 1099, 1329, 1447, 1449, 1621, 1647, 1699, 1819, 1917, 1963, 2233, 2457, 3111, 3153, 3163, 3247, 3373, 3513, 3679, 3747, 3777, 3889, 3919, 4249, 4263, 4627, 4839, 5233, 5847, 5899, 5907, 6037, 6211, 6331, 6457, 6577, 6607, 6621, 6697, 6751, 6961, 7117, 7243, 7257, 7279, 7383, 7417, 7497, 8277, 8661, 8719, 8773, 9223, 9277, 9289, 9469, 9519, 9541, 9573, 9667, 9679, 9757, 9859, 9867 }; const int n; // 入力文字列の大きさ std::string S; // 入力文字列 public: // コンストラクタ RollingHash(std::string &S_): n(S_.size()){ S = S_; init(); } // 初期化 inline void init(){ // modの選択 : まだ選ばれて居ない場合 if(mod_not_chosen){ std::random_device randRoll; std::vector prev(mod_size, -1); auto fn_bad = [&](int idx, int ptr){ for(int i = 0; i < idx; ++i) if(prev[i] == ptr) return true; mod[idx] = ptr; return false; }; rep(i, mod_size){ int a; do{a = randRoll() % Arr_Size_thePrimes; }while(fn_bad(i, a)); mod[i] = One_E_Nine - thePrimes[a]; } mod_not_chosen = false; } // 大きさの確保 power.resize(n+1, std::vector(base_size, V_LLi(mod_size, 1))); hash.resize(n+1, std::vector(base_size, V_LLi(mod_size, 0))); // 初期条件 // power[0][0] = 1; power[0][1] = 1; // hash[0] = {{0, 0}, {0, 0}}; // 実行 rep(itr, n) rep(i, base_size) rep(j, mod_size){ power[itr+1][i][j] = (power[itr][i][j] * base[i]) % mod[j]; hash[itr+1][i][j] = (hash[itr][i][j] * base[i] + S[itr]) % mod[j]; } } // ハッシュ値の取得 : [left, right) in 0-indexed inline LLi getHash(int left, int right, int b_id = 0, int m_id = 0){ LLi res = hash[right][b_id][m_id] - hash[left][b_id][m_id] * power[right-left][b_id][m_id] % mod[m_id]; if(res < 0) res += mod[m_id]; return res; } // s[start:] で lengthの長さのハッシュ値の取得 (0-indexed) inline LLi getHash_Length(int start, int length, int b_id = 0, int m_id = 0){ return getHash(start, start+length, b_id, m_id); } // sa..., と sb... の長さLの文字列が等しいかをHashを用いて判定 : 0-indexed inline bool sameOf(int a, int b, int L){ rep(i, base_size) rep(j, mod_size) if(getHash(a, a+L, i, j) != getHash(b, b + L, i, j)) return false; return true; } // 他の文字列のハッシュを用いて S[a:]とT[b:]の長さLの文字列の一致を判定 inline bool sameOf(RollingHash &T, int a, int b, int L){ rep(i, base_size) rep(j, mod_size) if(this->getHash_Length(a, L, i, j) != T.getHash_Length(b, L, i, j)) return false; return true; } // LCP of { S[a:] and S[b:] } in 0-indexed inline int getLCP(int a, int b){ if(a > b) std::swap(a, b); int ok = 0, ng = n - b + 1; while(ng - ok > 1){ int lngth = (ok + ng) / 2; if(sameOf(a, b, lngth)) ok = lngth; else ng = lngth; } return ok; } // 他の文字列のハッシュを用いて, S[a:] と T[b:]のLCPを取得 inline int getLCP_with(RollingHash &T, int a, int b){ int ok = 0, ng = std::min(T.n - b, this->n - a) + 1; while(ng - ok > 1){ int mid = (ng + ok) >> 1; if(sameOf(T, a, b, mid)) ok = mid; else ng = mid; } return ok; } // ABC141 より : 長さ length の交わりの共通連続部分文字列の存在を判定 O(NlogN) inline bool findCP(int length){ using pll = std::pair; std::map, int> theHash; for(int x = 0; x + length <= n; x++){ pll lp = {getHash_Length(x, length, 0, 0), getHash_Length(x, length, 0, 1)}; pll rp = {getHash_Length(x, length, 1, 0), getHash_Length(x, length, 1, 1)}; std::pair P = {lp, rp}; if(theHash.find(P) != theHash.end()) { if(x - theHash[P] >= length) return true; } else theHash[P] = x; } return false; } #undef rep }; // 静的メンバの初期化 bool RollingHash::mod_not_chosen = true; std::array RollingHash::mod; // ==================== ここまで ============================ constexpr int ALPHA = 'z' - 'a' + 1; std::vector indexes[ALPHA]; std::string S; int main(void){ std::cin >> S; const int L1 = S.size(); REP(i, L1) indexes[S[i]-'A'].push_back(i); RollingHash SS(S); int m; std::cin >> m; int cnt = 0; while(m--){ std::string T; std::cin >> T; RollingHash ST(T); const int L2 = T.size(); int p = T.front() - 'A'; for(int v : indexes[p]){ if(v + L2 > L1) break; if(SS.sameOf(ST, v, 0, L2)) cnt++; } } std::cout << cnt << '\n'; return 0; }