#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <set> #include <list> #include <cmath> #include <queue> #include <climits> #include <stack> #define FOR(i,p,k) for(int i = (p);i<(k);i++) typedef long long int LL; using namespace std; int n; LL mod = 1000000009; char z; LL acc_pot[3]; LL pot[3]; LL hash1[3], hash2[3]; void dane() { FOR(i,0,3) { acc_pot[i] = 1; } pot[0] = 37; pot[1] = 73; pot[2] = 61; cin>>n; while(cin>>z) { FOR(i,0,3) { hash1[i] = (hash1[i]*pot[i] + z)%mod; hash2[i] = (hash2[i] + z*acc_pot[i])%mod; acc_pot[i] = (acc_pot[i] * pot[i])%mod; } } int ile = 0; FOR(i,0,3) { if(hash1[i] == hash2[i]) { ile++; } } if(ile==3) { cout<<"TAK\n"; } else { cout<<"NIE\n"; } } int main() { ios_base::sync_with_stdio(false); dane(); 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 | #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <set> #include <list> #include <cmath> #include <queue> #include <climits> #include <stack> #define FOR(i,p,k) for(int i = (p);i<(k);i++) typedef long long int LL; using namespace std; int n; LL mod = 1000000009; char z; LL acc_pot[3]; LL pot[3]; LL hash1[3], hash2[3]; void dane() { FOR(i,0,3) { acc_pot[i] = 1; } pot[0] = 37; pot[1] = 73; pot[2] = 61; cin>>n; while(cin>>z) { FOR(i,0,3) { hash1[i] = (hash1[i]*pot[i] + z)%mod; hash2[i] = (hash2[i] + z*acc_pot[i])%mod; acc_pot[i] = (acc_pot[i] * pot[i])%mod; } } int ile = 0; FOR(i,0,3) { if(hash1[i] == hash2[i]) { ile++; } } if(ile==3) { cout<<"TAK\n"; } else { cout<<"NIE\n"; } } int main() { ios_base::sync_with_stdio(false); dane(); return 0; } |