H5.cpp

#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#define INF 2000000000
#define MAX 3000001
using namespace std;

int Z, n, pref1[MAX], pref2[MAX];
char text[MAX];
bool ok;

void load_data_and_cleaning();
void calculate();
void print_data();

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

void load_data_and_cleaning() {
  ok = false;
  scanf("%d", &n);
  scanf("%s", text);
  text[n] = '#';
  scanf("%s", text + n + 1);

  for (int i = n+1; i <= 2*n; i++) text[i+n] = text[i];
  n *= 3;
}

void make_pref1() {
  pref1[0] = pref1[1] = 0;
  int j = 1, t;
  for (int i = 1; i <= n; i++) {
    if (j+pref1[j] >= i) t = min(pref1[i-j], j+pref1[j]-i);
    else t = 0;
    while (i+t <= n && text[i+t] == text[t]) t++;
    pref1[i] = t;
    if (i + pref1[i] > j+pref1[j]) j = i;
  }
}

void make_pref2() {
  pref2[0] = pref2[1] = 0;
  int j = 1, t;
  for (int i = 1; i <= n; i++) {
    if(j+pref2[j] >= i) t = min(pref2[i-j], j+pref2[j]-i);
    else t = 0;
    while(i+t <= n && text[i+t] == text[t]) t++;
    pref2[i] = t;
    if (i + pref2[i] > j+pref2[j]) j = i;
  }
}

void calculate() {
  make_pref1();

  for (int i = 0; i < n/6; i++) swap(text[i], text[n/3-i-1]);
  for (int i = n/3+1; i <= n-n/3; i++) swap(text[i], text[n-i+n/3+1]);

  make_pref2();

  for (int i = n/3+1; i <= n-n/3; i++) swap(pref2[i], pref2[n-i+n/3+1]);
  for (int i = n/3+1; i <= n-n/3; i++) if(pref1[i]+pref2[i+n/3-1] >= n/3-1) ok = true;
}

void print_data() {
  printf((ok) ? "TAK" : "NIE");
  printf("\n");
}