N5.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#define INF 1000000009
#define MAX 1000009
#define MAX2 100009
#define mod 1000
#define REPEAT 5
#define PI 3.14159265
using namespace std;

typedef long long int ll;
typedef long double ld;

int Z, n, R, t, w, m, k, j, DBF[MAX], A[MAX];
char T[MAX], W[MAX2];
bool B[MAX];

void load_and_clean_data();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
  scanf("%d", &Z);
  while(Z--) {
    load_and_clean_data();
    calculate();
    print_data();
  }
  return 0;
}

bool comp(int x, int y) {
  return DBF[x] < DBF[y] || (DBF[x] == DBF[y] && DBF[min(t, x+k)]) < DBF[min(t,y+k)];
}

bool equal(int x, int y) {
  return DBF[x] == DBF[y] && DBF[min(t, x+k)] == DBF[min(t, y+k)];
}

void calculate_DBF() {
  for (int i = 0; i < t; i++) {
    DBF[i] = T[i]; A[i] = i;
  }
  DBF[t] = -1;
  for (k = 1; k <= 2*t; k *= 2) {
    sort(A, A+t, comp);
    for (int i = 1; i < t; i++) B[i] = !equal(A[i], A[i-1]);
    int key = 0;
    for (int i = 0; i < t; i++) {
      DBF[A[i]] = key;
      key += B[i+1];
    }
  }
}

bool check(int s) {
  for (int i = 0; A[s] + i <= t && i <= w; i++) {
    if (T[A[s] + i] > W[i]) return true;
    else if (T[A[s] + i] < W[i]) return false;
  }
  return true;
}

bool match(int s) {
  if(A[s] + w > t) return false;
  for (int i = 0; i < w; i++) if(T[A[s] + i] != W[i]) return false;
  return true;
}

void load_and_clean_data() {
  scanf("%s", T);
  t = strlen(T);
  calculate_DBF();
  for (int i = 0; i < t; i++) A[DBF[i]] = i;
  scanf("%d", &m);
}

void calculate() {
  while(m--) {
    scanf("%s", W);
    w = strlen(W);
    int b = -1, e = t-1, c;
    while(e-b>1) {
      c = (b+e)/2;
      if(check(c)) e = c;
      else b = c;
      if(match(e)) break;
    }
    printf(match(e) ? "TAK\n" : "NIE\n");
  }
}

void print_data() {
}