#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <set> #include <map> #include <string> #include <queue> #include <stack> using namespace std; typedef long long int LL; typedef long double LD; typedef vector<int> VI; typedef vector<LL> VLL; typedef vector<LD> VLD; typedef vector<string> VS; typedef pair<int, int> PII; typedef vector<PII> VPII; const int INF = 1000000001; const LD EPS = 10e-9; #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define MP make_pair #define PB push_back #define ST first #define ND second #define abs(a) ((a)<0 ? -(a) : (a)) #define max(a, b) ((a) > (b) ? (a) : (b)) #define min(a, b) ((a) < (b) ? (a) : (b)) const int MAX_N = 1000005; int n; const LL P19 = 1000000009; LL leftHash31, rightHash31, pow31 = 1; const LL P17 = 1073676287; LL leftHash37, rightHash37, pow37 = 1; const LL P21 = 2000000011; LL leftHash53, rightHash53, pow53 = 1; char c; void updateHash31() { leftHash31 = (31*leftHash31 + (c-'a')) % P19; rightHash31 = (rightHash31 + pow31*(c-'a')) % P19; pow31 = (pow31 * 31) % P19; } void updateHash37() { leftHash37 = (37*leftHash37 + (c-'a')) % P17; rightHash37 = (rightHash37 + pow37*(c-'a')) % P17; pow37 = (pow37 * 37) % P17; } void updateHash53() { leftHash53 = (53*leftHash53 + (c-'a')) % P21; rightHash53 = (rightHash53 + pow53*(c-'a')) % P21; pow53 = (pow53 * 53) % P21; } bool isPalindrome() { return (leftHash31 == rightHash31) && (leftHash37 == rightHash37) && (leftHash53 == rightHash53); } int main() { scanf("%d", &n); getchar(); while(true) { c = getchar(); if(c == '\n' || !isalnum(c)) break; updateHash31(); updateHash37(); updateHash53(); } printf((isPalindrome() ? "TAK\n" : "NIE\n")); return 0; }
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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <set> #include <map> #include <string> #include <queue> #include <stack> using namespace std; typedef long long int LL; typedef long double LD; typedef vector<int> VI; typedef vector<LL> VLL; typedef vector<LD> VLD; typedef vector<string> VS; typedef pair<int, int> PII; typedef vector<PII> VPII; const int INF = 1000000001; const LD EPS = 10e-9; #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define MP make_pair #define PB push_back #define ST first #define ND second #define abs(a) ((a)<0 ? -(a) : (a)) #define max(a, b) ((a) > (b) ? (a) : (b)) #define min(a, b) ((a) < (b) ? (a) : (b)) const int MAX_N = 1000005; int n; const LL P19 = 1000000009; LL leftHash31, rightHash31, pow31 = 1; const LL P17 = 1073676287; LL leftHash37, rightHash37, pow37 = 1; const LL P21 = 2000000011; LL leftHash53, rightHash53, pow53 = 1; char c; void updateHash31() { leftHash31 = (31*leftHash31 + (c-'a')) % P19; rightHash31 = (rightHash31 + pow31*(c-'a')) % P19; pow31 = (pow31 * 31) % P19; } void updateHash37() { leftHash37 = (37*leftHash37 + (c-'a')) % P17; rightHash37 = (rightHash37 + pow37*(c-'a')) % P17; pow37 = (pow37 * 37) % P17; } void updateHash53() { leftHash53 = (53*leftHash53 + (c-'a')) % P21; rightHash53 = (rightHash53 + pow53*(c-'a')) % P21; pow53 = (pow53 * 53) % P21; } bool isPalindrome() { return (leftHash31 == rightHash31) && (leftHash37 == rightHash37) && (leftHash53 == rightHash53); } int main() { scanf("%d", &n); getchar(); while(true) { c = getchar(); if(c == '\n' || !isalnum(c)) break; updateHash31(); updateHash37(); updateHash53(); } printf((isPalindrome() ? "TAK\n" : "NIE\n")); return 0; } |