H2.cpp

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

int Z, n, pi[MAX], d;
string lyr, regexp, full_text;
bool result;

void load_data();
void cleaning();
void calculate();
void print_data();

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

void load_data() {
  int nil;
  cin >> nil;
  cin >> lyr;
  cin >> regexp;
}

void cleaning() {

}

void calculate_pi() {
  pi[0] = pi[1] = 0;
  int j = 2;
  int t = 0;
  for (j = 2; j <= full_text.length(); j++) {
    while (t > 0 && (full_text[t] != full_text[j-1])) t = pi[t];
    if (full_text[t] == full_text[j-1]) t++;
    pi[j] = t;
  }
}

bool is_good() {
  calculate_pi();

  for (int i = 0; i < full_text.length(); i++) {
    if (pi[i] == lyr.length()) return true;
  }
  return false;
}

void calculate() {
  full_text = regexp + '@' + lyr + lyr;
  result = is_good();

  if (!result) {
    reverse(regexp.begin(), regexp.end());
    full_text.replace(0, lyr.length() , regexp);
    result = is_good();
  }
}

void print_data() {
  cout << ((result) ? "IDENTYCZNE" : "ROZNE");
  cout << endl;
}