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 <vector>
#include <algorithm>
#include <iterator>
#include <cctype>

using namespace std;

#define DEBUG false
#define LOG if (DEBUG) cout
typedef long long ll;
typedef int pt;
const int BUFFER_SIZE = 100000;
const int BASE = 26;
const int PRIME_SIZE = 10;

pt primes[PRIME_SIZE] = { 75000007, 75000017, 75000031, 75000047, 75000071, 75000083, 75000097, 75000103, 75000113, 75000143 };
char buffer[BUFFER_SIZE + 1];

void fill(pt* arr, int value) {
    for (int i = 0; i < PRIME_SIZE; i++) {
        arr[i] = value;
    }
}

int main() {
    int n;
    ios_base::sync_with_stdio(false);
    pt backwards[PRIME_SIZE], forwards[PRIME_SIZE], powers[PRIME_SIZE];
    
    cin >> n;
    fill(powers, 1);
    fill(forwards, 0);
    fill(backwards, 0);
    int count, i;    
    
    do {
        cin.read(buffer, BUFFER_SIZE);
        count = cin.gcount();
        
        for (i = 0; i < count; i++) {
            char c = buffer[i];
            if (!isalpha(c)) continue;
            
            int letter = c - 'a';
            
            for (int j = 0; j < PRIME_SIZE; j++) {
                forwards[j] = (forwards[j]*BASE + letter) % primes[j];
                backwards[j] = (backwards[j] + powers[j]*letter) % primes[j];
                powers[j] = (powers[j] * BASE) % primes[j];
            }
        }
    } while (count > 0);
    
    for (i = 0; i < PRIME_SIZE; i++) {
        if (forwards[i] != backwards[i]) break;
    }
    
    if (i == PRIME_SIZE) {
        cout << "TAK";
    } else {
        cout << "NIE";
    }
        
    return 0;
}

// https://www.geeksforgeeks.org/online-algorithm-for-checking-palindrome-in-a-stream/
// http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php