#include //#include using namespace std; // using namespace atcoder; // using mint = modint1000000007; // const int mod = 1000000007; // using mint = modint998244353; // const int mod = 998244353; // const int INF = 1e9; // const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i, l, r) for (int i = (l); i < (r); ++i) #define rrep(i, n) for (int i = (n)-1; i >= 0; --i) #define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define P pair template inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; } #ifndef KWM_T_STRING_ROLLING_HASH_HPP #define KWM_T_STRING_ROLLING_HASH_HPP #include #include /** * @brief Rolling Hash(静的・ダブルハッシュ) * * 文字列や配列に対して prefix hash を構築し、 * 任意区間のハッシュを O(1) で取得できる * * 計算量: * 構築: O(N) * クエリ: O(1) * * @tparam T 要素型(char, int など) * * @param s 入力列 * * 使用例: * RollingHash rh(s); * auto h = rh.get(l, r); // [l, r) * * if (rh.get(l1, r1) == rh.get(l2, r2)) { * // substring equal * } * * 制約 / 注意: * - 衝突の可能性は低いがゼロではない * - T は整数として扱える必要あり * * verified: * - substring一致判定 * - 回文判定 */ namespace kwm_t::string { template struct RollingHash { private: using ll = long long; static constexpr ll base1 = 1007; static constexpr ll base2 = 2009; static constexpr ll mod1 = 1000000007; static constexpr ll mod2 = 1000000009; std::vector hash1, hash2; std::vector power1, power2; public: RollingHash() = default; explicit RollingHash(const Container& s) { build(s); } void build(const Container& s) { int n = (int)s.size(); hash1.assign(n + 1, 0); hash2.assign(n + 1, 0); power1.assign(n + 1, 1); power2.assign(n + 1, 1); for (int i = 0; i < n; ++i) { ll x = (ll)s[i]; hash1[i + 1] = (hash1[i] * base1 + x) % mod1; hash2[i + 1] = (hash2[i] * base2 + x) % mod2; power1[i + 1] = (power1[i] * base1) % mod1; power2[i + 1] = (power2[i] * base2) % mod2; } } /** * @brief 区間 [l, r) のハッシュを取得 */ std::pair get(int l, int r) const { ll res1 = hash1[r] - hash1[l] * power1[r - l] % mod1; if (res1 < 0) res1 += mod1; ll res2 = hash2[r] - hash2[l] * power2[r - l] % mod2; if (res2 < 0) res2 += mod2; return { res1, res2 }; } /** * @brief 長さを取得 */ int size() const { return (int)hash1.size() - 1; } }; } // namespace kwm_t::string #endif // KWM_T_STRING_ROLLING_HASH_HPP int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); string s; cin >> s; int m; cin >> m; kwm_t::string::RollingHash rh(s); vector>mp(11); int n = s.size(); rep2(i, 1, 11) { rep(l, n) { int r = l + i; if (r > n)break; mp[i][rh.get(l, r)]++; } } long long ans = 0; while (m--) { string s; cin >> s; kwm_t::string::RollingHash rh(s); auto hash = rh.get(0, s.size()); ans += mp[s.size()][hash]; } cout << ans << endl; return 0; }