# include # include #include # include #include #include #include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include #include #include #include #include #include //#include using namespace std; using LL = int; using ULL = unsigned long long; long long MOD = 1000000000 + 7; constexpr long long INF = numeric_limits::max(); const double PI = acos(-1); #define fir first #define sec second #define thi third #define debug(x) cerr<<#x<<": "< Pll; typedef pair> Ppll; typedef pair>> Pbll; typedef pair>> Pvll; typedef pair Vec2; struct Tll { LL first, second, third; }; struct Fll { LL first, second, third, fourd; }; typedef pair Ptll; #define rep(i,rept) for(LL i=0;i=0;i--) LL h, w, n, m, k, t, s, q, last, cnt, sum, ans, dp[10000], a[2000000], b[2000000]; string str, ss; bool f[1100][1100]; char c; int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } }; struct Edge { LL to, cost; }; vectorvec[200000]; listli[20000]; vectorv; map>ma; multisetst[3]; void YN(bool f) { if (f) cout << "YES" << endl; else cout << "NO" << endl; } void yn(bool f) { if (f) cout << "Yes" << endl; else cout << "No" << endl; } const int _base = 1e9 + 7; struct RollingHash { string former; int sz; vector< unsigned > hashed, power; vectoridx; RollingHash(const string& s) { //文字列sのハッシュテーブルを構築する former = s; sz = s.size(); idx.resize(sz); hashed.assign(sz + 1, 0); power.assign(sz + 1, 0); power[0] = 1; for (int i = 0; i < sz; i++) { power[i + 1] = power[i] * _base; } for (int i = 0; i < sz; i++) { hashed[i + 1] = (hashed[i] + s[i]) * _base; } iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](const int& a, const int& b) { int low = 0, high = min(sz - a, sz - b) + 1; while (high - low > 1) { int mid = (low + high) >> 1; if (get(a, a + mid) == get(b, b + mid)) low = mid; else high = mid; } if (low == min(sz - a, sz - b)) return (low == sz - a); return (former[a + low] < former[b + low]); }); } bool comp(RollingHash& hashed1, const int& b) { int mm = hashed1.hashed.size() - 1; int low = 0, high = min(mm, sz - b) + 1; while (high - low > 1) { int mid = (low + high) >> 1; if (hashed1.get(0, mid) == get(b, b + mid)) low = mid; else high = mid; } if (low == min(mm, sz - b)) return (low == mm); return (hashed1.former[low] < former[b + low]); } unsigned get(int l, int r) { //区間[l,r)のハッシュ値を求める return((hashed[r] - hashed[l] * power[r - l])); } unsigned connect(int h1, int h2, int h2len) { //ハッシュ値h1と長さh2lenのハッシュ値h2を結合する return(h1 * power[h2len] + h2); } int LCP(RollingHash& b, int l1, int r1, int l2, int r2) { //区間[l1,r1)とハッシュテーブルがbからなる区間[l2,r2)の文字列の最長共通接頭辞の長さを求める int len = min(r1 - l1, r2 - l2); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) >> 1; if (get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid; else high = mid; } return(low); } int contain(RollingHash& b) { unsigned val = b.get(0, b.former.size()); int low1 = -1, high1 = former.size() - 1; while (high1 - low1 > 1) { int mid = (low1 + high1) >> 1; if (comp(b, idx[mid])) high1 = mid; else low1 = mid; } if (val != get(idx[high1], idx[high1] + b.former.size())) return 0; int low2 = high1, high2 = former.size(); while (high2 - low2 > 1) { int mid = (low2 + high2) >> 1; if (val == get(idx[mid], idx[mid] + b.former.size())) low2 = mid; else high2 = mid; } return low2 - high1 + 1; } }; int main() { cin >> str; RollingHash cur(str); cin >> n; rep(i, n) { cin >> ss; RollingHash nex(ss); ans+=cur.contain(nex); } cout << ans << endl; return 0; }