#include <cstdio> using namespace std; const long long p = 257; const long long M = 100000007; // H(s) = s_0*1 + s_1*p^1 + s_2*p^2 ... s_n*p^n long long fast_pow(long long base, long long power, long long modulus){ long long result = 1; while(power > 0){ if(power & 1 == 1){ result = (result * base) % modulus; } power >>= 1; base = ( base*base ) % modulus; } return result; } // H(c + s) = c + H(s)*p long long add_front(long long hash, char ch){ return (hash*p + (long long)ch) % M; } // H(s + c) = H(s) + c*p^s.length int add_back(long long hash, char ch, int length){ return (hash + (long long)ch*fast_pow(p, length, M)) % M; } int main(){ int n; scanf("%d", &n); n = 0; char c; c=getchar(); while(c < 'a' || c > 'z') c = getchar(); long long hash1=0, hash2=0; while ( c >= 'a' && c <= 'z' ) { hash1 = add_front(hash1, c); hash2 = add_back(hash2, c, n); c=getchar(); n++; } if(hash1 == hash2) printf("TAK\n"); else printf("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 | #include <cstdio> using namespace std; const long long p = 257; const long long M = 100000007; // H(s) = s_0*1 + s_1*p^1 + s_2*p^2 ... s_n*p^n long long fast_pow(long long base, long long power, long long modulus){ long long result = 1; while(power > 0){ if(power & 1 == 1){ result = (result * base) % modulus; } power >>= 1; base = ( base*base ) % modulus; } return result; } // H(c + s) = c + H(s)*p long long add_front(long long hash, char ch){ return (hash*p + (long long)ch) % M; } // H(s + c) = H(s) + c*p^s.length int add_back(long long hash, char ch, int length){ return (hash + (long long)ch*fast_pow(p, length, M)) % M; } int main(){ int n; scanf("%d", &n); n = 0; char c; c=getchar(); while(c < 'a' || c > 'z') c = getchar(); long long hash1=0, hash2=0; while ( c >= 'a' && c <= 'z' ) { hash1 = add_front(hash1, c); hash2 = add_back(hash2, c, n); c=getchar(); n++; } if(hash1 == hash2) printf("TAK\n"); else printf("NIE\n"); return 0; } |