#include <iostream> #include <vector> #include <algorithm> using namespace std; #define ll long long long long compute_hash(string const& s) { const int p = 31; const int m = 1e9 + 9; long long hash_value = 0; long long p_pow = 1; for (char c : s) { hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m; p_pow = (p_pow * p) % m; } return hash_value; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; char c; ll l1 = 0, l2 = 0, r1 = 0, r2 = 0,p1 = 31, p2 = 33, m1 = 1e9 + 9, m2 = 1e9 + 6421, P1 = 1, P2 = 1, cc; while(cin >> c) { cc = c - 'a' + 1; l1 = (l1 + P1 * cc) % m1; P1 = (P1 * p1) % m1; l2 = (l2 + P2 * cc) % m2; P2 = (P2 * p2) % m2; r1 = (p1 * r1 + cc) % m1; r2 = (p2 * r2 + cc) % m2; } if(l1 == r1 && l2 == r2) cout << "TAK"; else cout << "NIE"; 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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; #define ll long long long long compute_hash(string const& s) { const int p = 31; const int m = 1e9 + 9; long long hash_value = 0; long long p_pow = 1; for (char c : s) { hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m; p_pow = (p_pow * p) % m; } return hash_value; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; char c; ll l1 = 0, l2 = 0, r1 = 0, r2 = 0,p1 = 31, p2 = 33, m1 = 1e9 + 9, m2 = 1e9 + 6421, P1 = 1, P2 = 1, cc; while(cin >> c) { cc = c - 'a' + 1; l1 = (l1 + P1 * cc) % m1; P1 = (P1 * p1) % m1; l2 = (l2 + P2 * cc) % m2; P2 = (P2 * p2) % m2; r1 = (p1 * r1 + cc) % m1; r2 = (p2 * r2 + cc) % m2; } if(l1 == r1 && l2 == r2) cout << "TAK"; else cout << "NIE"; return 0; } |