#include using namespace std; #define rep(i,a,b) for(int i=a;i vi; typedef long long ll; struct RollingHash { static const ll mo0 = 1000000007, mo1 = 1000000009; static ll mul0, mul1; static const ll add0 = 1000010007, add1 = 1003333331; static vector pmo[2]; vector s; int l; vector hash_[2]; void init(vector s) { this->s = s; l = s.size(); int i, j; hash_[0] = hash_[1] = vector(1, 0); if (!mul0) mul0 = 10009 + (((ll)&mul0) >> 5) % 259, mul1 = 10007 + (((ll)&mul1) >> 5) % 257; if (pmo[0].empty()) pmo[0].push_back(1), pmo[1].push_back(1); for (int i = 0; i < l; i++) hash_[0].push_back((hash_[0].back()*mul0 + add0 + s[i]) % mo0); for (int i = 0; i < l; i++) hash_[1].push_back((hash_[1].back()*mul1 + add1 + s[i]) % mo1); } pair hash(int l, int r) { // s[l..r] if (l>r) return make_pair(0, 0); while (pmo[0].size() RollingHash::pmo[2]; ll RollingHash::mul0, RollingHash::mul1; //----------------------------------------------------------------- string S; int M; string C[5010]; //----------------------------------------------------------------- int main() { cin >> S >> M; rep(i, 0, M) cin >> C[i]; RollingHash HashS; vi VS(S.length()); rep(i, 0, S.length()) VS[i] = S[i] - 'a'; HashS.init(VS); int ans = 0; rep(i, 0, M) { RollingHash HashC; vi VC(C[i].length()); rep(j, 0, C[i].length()) VC[j] = C[i][j] - 'a'; HashC.init(VC); rep(j, 0, S.length() - (C[i].length() - 1)) { auto s = HashS.hash(j, j + C[i].length() - 1); auto c = HashC.hash(0, C[i].length() - 1); if (s == c) ans++; } } cout << ans << endl; }