#include <stdio.h>
#include <string.h>

#define Nadejde 1000005
#define Smerenie 10005
#define MAX_WORD 1005
#define MAX_UTF8 256
#define Sigma 26

/** Algoritmul Aho-Corasick.
 * Multumim Doamne!
**/

// Structura trie.
struct trie {
    int freq;
    trie *fail;
    trie *child[Sigma + 1];

    trie() {
      freq = 0;
      fail = NULL;
      memset(child, NULL, sizeof(child));
    }
};

int N;
char s[Nadejde];
int qhead, qtail;
int type[MAX_UTF8];             // type[i] este numarul de ordine pentru caracterul "i".
char word[Smerenie];            // cuvantul urmator din dictionar.
trie *fin[MAX_WORD];            // rezultatul se afla in "fin" -> "freq".
trie *root = new trie;          // radacina.
trie *Q[Smerenie * MAX_WORD];   // coada bfs().

/** Initializeaza "type". **/
void init() {
  char i;
  for (i = 'a'; i <= 'z'; i++) {
    type[i] = i - 'a' + 1;
  }
}

/** Adauga in trie caracterul "p" din cuvantul "i". **/
void add(trie *curr, char *p, int i) {
  int c = type[*p];
  if (!c) {
    fin[i] = curr;
    return ;
  }
  if (curr -> child[c] == NULL) {
    curr -> child[c] = new trie;
  }
  add(curr -> child[c], p + 1, i);
}

/** Parcurge in latime trie-ul. **/
void bfs() {
  int i;
  trie *curr, *suff;

  qhead = qtail = 1;
  Q[qtail] = root;
  root -> fail = root;
  while (qhead <= qtail) {
    curr = Q[qhead++];
    for (i = 1; i <= Sigma; i++) {
      if (curr -> child[i] != NULL) {
        suff = curr -> fail;
        while ((suff -> child[i] == NULL) && (suff != root)) {
          suff = suff -> fail;
        }
        if ((suff -> child[i] != NULL) && (suff -> child[i] != curr -> child[i])) {
          curr -> child[i] -> fail = suff -> child[i];
        } else {
          curr -> child[i] -> fail = root;
        }
        Q[++qtail] = curr -> child[i];
      }
    }
  }
}

int main(void) {
  int i, c;
  FILE *f = fopen("ahocorasick.in", "r");

  /* Citeste sirul nostru. */
  fgets(s, Nadejde, f);
  fscanf(f, "%d\n", &N);
  init();

  for (i = 1; i <= N; i++) {
    fgets(word, Smerenie, f);
    add(root, word, i);
  }
  fclose(f);

  f = fopen("ahocorasick.out", "w");

  bfs();

  /* Determina numarul aparitiilor cuvintelor in sir. **/
  trie *curr = root;
  int len = strlen(s) - 1;
  for (i = 0; i < len; i++) {
    c = type[s[i]];
    while ((curr != root) && (curr -> child[c] == NULL)) {
      curr = curr -> fail ;
    }
    if (curr -> child[c] != NULL) {
      curr = curr -> child[c];
    }
    curr -> freq++;
  }
  for (i = qtail; i; i--) {
    Q[i] -> fail -> freq += Q[i] -> freq;
  }
  for (i = 1; i <= N; i++) {
    fprintf(f, "%d\n", fin[i] -> freq);
  }
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}