1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>

// d is the number of characters in input alphabet 
#define d 32 

// q is a prime number used for evaluating Rabin Karp's Rolling hash 
#define q1 1000000007 
#define q2 1000000009 

using namespace std;

int main()
{
	int a[256];
	for (int i = 0; i < 256; ++i)
		a[i] = 0;
	for (int i = 'a'; i <= 'z'; ++i)
		a[i] = 1;

	int n = 0;
	scanf("%d\n", &n);

	int ch = getchar() & 31;
	long long fh1 = ch % q1;
	long long rh1 = fh1;
	long long fh2 = ch % q2;
	long long rh2 = fh2;
	long long h1 = 1;
	long long h2 = 1;

	while ((ch = getchar()) != EOF)
	{
		if (a[ch] == 0)
			break;
		ch &= 31;

		h1 = (h1*d) % q1;
		fh1 = (fh1 + h1*ch) % q1;
		rh1 = (rh1*d + ch) % q1;

		h2 = (h2*d) % q2;
		fh2 = (fh2 + h2*ch) % q2;
		rh2 = (rh2*d + ch) % q2;
		n++;
	}

	if ((fh1 == rh1) && (fh2 == rh2))
		printf("%s", "TAK");
	else
		printf("%s", "NIE");
	return 0;
}