#include <iostream> using namespace std; typedef unsigned long ttype; const ttype MOD_A = 9999991; const ttype BASE_A = 2; const ttype MOD_B = 10000019; const ttype BASE_B = 257; inline void solve() { ttype hash_left_a = 0; ttype hash_right_a = 0; ttype base_a = BASE_A; ttype hash_left_b = 0; ttype hash_right_b = 0; ttype base_b = BASE_B; int size; cin >> size; char ch; do { ch = cin.get(); } while (ch < 'a' || ch > 'z'); ch = ch - 'a'; { hash_left_a = ch; hash_right_a = ch; } { hash_left_b = ch; hash_right_b = ch; } ch = cin.get(); while (ch >= 'a' && ch <= 'z') { ch = ch - 'a'; { hash_left_a += ch * base_a; hash_left_a %= MOD_A; base_a *= BASE_A; base_a %= MOD_A; hash_right_a *= BASE_A; hash_right_a += ch; hash_right_a %= MOD_A; } { hash_left_b += ch * base_b; hash_left_b %= MOD_B; base_b *= BASE_B; base_b %= MOD_B; hash_right_b *= BASE_B; hash_right_b += ch; hash_right_b %= MOD_B; } ch = cin.get(); } cout << ((hash_left_a == hash_right_a) && (hash_left_b == hash_right_b) ? "TAK" : "NIE") << endl; } int main(int argc, char **argv) { ios_base::sync_with_stdio(0); solve(); 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 | #include <iostream> using namespace std; typedef unsigned long ttype; const ttype MOD_A = 9999991; const ttype BASE_A = 2; const ttype MOD_B = 10000019; const ttype BASE_B = 257; inline void solve() { ttype hash_left_a = 0; ttype hash_right_a = 0; ttype base_a = BASE_A; ttype hash_left_b = 0; ttype hash_right_b = 0; ttype base_b = BASE_B; int size; cin >> size; char ch; do { ch = cin.get(); } while (ch < 'a' || ch > 'z'); ch = ch - 'a'; { hash_left_a = ch; hash_right_a = ch; } { hash_left_b = ch; hash_right_b = ch; } ch = cin.get(); while (ch >= 'a' && ch <= 'z') { ch = ch - 'a'; { hash_left_a += ch * base_a; hash_left_a %= MOD_A; base_a *= BASE_A; base_a %= MOD_A; hash_right_a *= BASE_A; hash_right_a += ch; hash_right_a %= MOD_A; } { hash_left_b += ch * base_b; hash_left_b %= MOD_B; base_b *= BASE_B; base_b %= MOD_B; hash_right_b *= BASE_B; hash_right_b += ch; hash_right_b %= MOD_B; } ch = cin.get(); } cout << ((hash_left_a == hash_right_a) && (hash_left_b == hash_right_b) ? "TAK" : "NIE") << endl; } int main(int argc, char **argv) { ios_base::sync_with_stdio(0); solve(); return 0; } |