#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; #define rep(i, j, n) for (int i = j; i < (n); ++i) #define rrep(i, j, n) for (int i = (n)-1; j <= i; --i) template vector search(const vector& s, const vector& pattern) { vector table(pattern.size() + 1); // table[i] := when pattern[i] is not matched, next start from // pattern[table[i]] table[0] = -1; for (int i = 0, len = -1; i < (int)pattern.size(); ++i) { while (len >= 0 && pattern[i] != pattern[len]) len = table[len]; ++len; table[i + 1] = len; } vector pos; for (int i = 0, len = 0; i < (int)s.size(); ++i) { while (len >= 0 && s[i] != pattern[len]) len = table[len]; ++len; if (len == pattern.size()) { pos.push_back(i - len + 1); len = table[len]; } } return pos; } int main() { cin.tie(0)->sync_with_stdio(0); string ts; cin >> ts; vector s(ts.begin(), ts.end()); int m; cin >> m; int ans = 0; for (int i = 0; i < m; ++i) { string tc; cin >> tc; vector c(tc.begin(), tc.end()); vector res = search(s, c); ans += res.size(); } cout << ans << '\n'; return 0; }