#include <cstdio> const int P = 65697811, MOD = 1951323287; int n; char c; unsigned long long hash[26], revhash[26], pow[26], sumpow[26]; int main() { scanf("%d\n", &n); n = 0; for (int i=0; i<26; i++) pow[i] = 1; while ((c = getchar()) >= 'a') { c -= 'a'; hash[c] = (P * hash[c] + n) % MOD; revhash[c] = (revhash[c] + n * pow[c]) % MOD; sumpow[c] = (sumpow[c] + pow[c]) % MOD; pow[c] = (P * pow[c]) % MOD; n++; } bool ans = true; for (int i=0; i<26; i++) { unsigned long long x = ((n-1) * sumpow[i]) % MOD; x = (x + MOD - revhash[i]) % MOD; ans = (ans && x == hash[i]); } printf(ans ? "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 | #include <cstdio> const int P = 65697811, MOD = 1951323287; int n; char c; unsigned long long hash[26], revhash[26], pow[26], sumpow[26]; int main() { scanf("%d\n", &n); n = 0; for (int i=0; i<26; i++) pow[i] = 1; while ((c = getchar()) >= 'a') { c -= 'a'; hash[c] = (P * hash[c] + n) % MOD; revhash[c] = (revhash[c] + n * pow[c]) % MOD; sumpow[c] = (sumpow[c] + pow[c]) % MOD; pow[c] = (P * pow[c]) % MOD; n++; } bool ans = true; for (int i=0; i<26; i++) { unsigned long long x = ((n-1) * sumpow[i]) % MOD; x = (x + MOD - revhash[i]) % MOD; ans = (ans && x == hash[i]); } printf(ans ? "TAK\n" : "NIE\n"); return 0; } |