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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <string>

using namespace std;

const long long numberOfLetters = 26; 
const long long prime = 103;

void checkPalindrome() 
{
	string answer = "NIE";
	bool read = false;
	int lastTime = 1;

	char c;
	long long h = 1;
	long long i = 1;
	long long j = 0; 
	string str = "";

	cin.get(c);
	str += c;
	long long firstHalf = str[0] % prime; 
	if (!cin.get(c)) {
	    answer = "TAK";
		cout << answer;
		return;
	}
	str += c;
	long long secondHalf = str[1] % prime; 

	while(cin.get(c) || (c >= 97 && c <= 122 && lastTime--)) {
		str += c;

		if (firstHalf == secondHalf)
		{ 
			for (j = 0; j < i/2; j++) 
			{ 
				if (str[j] != str[i-j]) 
					break; 
			} 
			answer = (j == i/2) ? "TAK" : "NIE"; 
		} 
		else answer = "NIE";

		if (c >= 97 && c <= 122) {
			if (i % 2 == 0) 
			{ 
				h = (h * numberOfLetters) % prime; 
				firstHalf = (firstHalf + h * str[i/2]) % prime; 
				secondHalf = (secondHalf * numberOfLetters + str[i+1]) % prime; 
			} 
			else
			{ 
				secondHalf = (numberOfLetters * (secondHalf + prime - str[(i + 1) / 2] * h) % prime + str[i+1]) % prime; 
			} 
		}
		i++;
	};
	cout << answer;
} 

int main() 
{
	string str;
	getline(cin, str);
	checkPalindrome(); 
	return 0; 
}