/* ID: espr1t TASK: KEYWORDS: */ #include #include #include #include #include using namespace std; FILE *in; FILE *out; const int MAX = 500005; const int MM = 5005; int n, m; char a[MAX], b[MAX]; int table[MM]; // Knuth-Morris-Pratt int eval() { int ans = 0; // Precalc Function table[0] = -1; table[1] = 0; int match = 0; for (int i = 2; i <= m; i++) { while (match > 0 && b[i - 1] != b[match]) match = table[match]; if (b[i - 1] == b[match]) match++; table[i] = match; } // Knuth-Morris-Pratt matcher match = 0; for (int i = 0; i < n; i++) { while (match > 0 && a[i] != b[match]) match = table[match]; if (a[i] == b[match]) match++; if (match >= m) { ans++; match = table[match]; } } return ans; } /* const int MOD1 = 34482743, BASE1 = 29; const int MOD2 = 32258059, BASE2 = 31; const int MOD3 = 27027019, BASE3 = 37; int pwr1[MM], pwr2[MM], pwr3[MM]; int eval() { if (m > n) return 0; int s1 = 0, s2 = 0, s3 = 0; for (int i = 0; i < m; i++) { s1 = (s1 * BASE1 + b[i] - 'a' + 1) % MOD1; s2 = (s2 * BASE2 + b[i] - 'a' + 1) % MOD2; // s3 = (s3 * BASE3 + b[i] - 'a' + 1) % MOD3; } int h1 = 0, h2 = 0, h3 = 0; for (int i = 0; i < m; i++) { h1 = (h1 * BASE1 + a[i] - 'a' + 1) % MOD1; h2 = (h2 * BASE2 + a[i] - 'a' + 1) % MOD2; // h3 = (h3 * BASE3 + a[i] - 'a' + 1) % MOD3; } int ans = 0; if (h1 == s1 && h2 == s2 && h3 == s3) ans++; for (int i = m; i < n; i++) { h1 -= (pwr1[m - 1] * (a[i - m] - 'a' + 1)) % MOD1; if (h1 < 0) h1 += MOD1; h2 -= (pwr2[m - 1] * (a[i - m] - 'a' + 1)) % MOD2; if (h2 < 0) h2 += MOD2; // h3 -= (pwr3[m - 1] * (a[i - m] - 'a' + 1)) % MOD3; if (h3 < 0) h3 += MOD3; h1 = (h1 * BASE1 + a[i] - 'a' + 1) % MOD1; h2 = (h2 * BASE2 + a[i] - 'a' + 1) % MOD2; // h3 = (h3 * BASE3 + a[i] - 'a' + 1) % MOD3; if (h1 == s1 && h2 == s2 && h3 == s3) ans++; } return ans; } void init() { pwr1[0] = pwr2[0] = pwr3[0] = 1; for (int i = 1; i < MM; i++) { pwr1[i] = (pwr1[i - 1] * BASE1) % MOD1; pwr2[i] = (pwr2[i - 1] * BASE2) % MOD2; pwr3[i] = (pwr3[i - 1] * BASE3) % MOD3; } } */ int main(void) { in = stdin; out = stdout; in = fopen("clown.in", "rt"); out = fopen("clown.out", "wt"); fscanf(in, "%s", a); n = (int)strlen(a); int numQueries; fscanf(in, "%d", &numQueries); for (int i = 0; i < numQueries; i++) { fscanf(in, "%s", b); m = (int)strlen(b); fprintf(out, "%d\n", eval()); } return 0; }