#include<iostream> #include<list> #include<stdio.h> #include<map> #include<set> #include<vector> using namespace std; #define ull unsigned long long int #define FOR(i,n) for(int i=0;i<(n);++i) #define FORI(i,start,n) for(int i=(start);i<(n);++i) #define FORit(it,collection) for(auto it = collection.cbegin(); it != collection.cend(); it++) #define SKIP -5000 #define znakow 26 #define DEBUG 0 #define dcout DEBUG && cout int inline min(int a,int b){return a>b?b:a;} int inline max(int a,int b){return a<b?b:a;} int main(){ int n; scanf("%d", &n); //cin>>n; char c; ull leftHash0=0, rightHash0=0; ull leftHash1=0, rightHash1=0; ull leftHash2=0, rightHash2=0; ull leftHash3=0, rightHash3=0; ull ck0=1; ull ck1=1; ull ck2=1; ull ck3=1; do {scanf("%c", &c);} while((c<'a') || ('z'<c)); do {//printf(":%c:\n", c); ull cc=c-'a'+1; rightHash0=(rightHash0*29+cc)%((1<<30)-1); leftHash0=(leftHash0+ck0*cc)%((1<<30)-1); ck0=(ck0*29)%((1<<30)-1); rightHash1=(rightHash1*31+cc)%999999937; leftHash1=(leftHash1+ck1*cc)%999999937; ck1=(ck1*31)%999999937; rightHash2=(rightHash2*421+cc)%999999677; leftHash2=(leftHash2+ck2*cc)%999999677; ck2=(ck2*421)%999999677; rightHash3=(rightHash3*37+cc)%1000000007; leftHash3=(leftHash3+ck3*cc)%1000000007; ck3=(ck3*37)%1000000007; if(scanf("%c", &c)!=1)break; } while(('a'<=c) & (c<='z')); if(leftHash0!=rightHash0 || leftHash1!=rightHash1 || leftHash2!=rightHash2 || leftHash3!=rightHash3){ printf("NIE\n"); return 0; } printf("TAK\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 | #include<iostream> #include<list> #include<stdio.h> #include<map> #include<set> #include<vector> using namespace std; #define ull unsigned long long int #define FOR(i,n) for(int i=0;i<(n);++i) #define FORI(i,start,n) for(int i=(start);i<(n);++i) #define FORit(it,collection) for(auto it = collection.cbegin(); it != collection.cend(); it++) #define SKIP -5000 #define znakow 26 #define DEBUG 0 #define dcout DEBUG && cout int inline min(int a,int b){return a>b?b:a;} int inline max(int a,int b){return a<b?b:a;} int main(){ int n; scanf("%d", &n); //cin>>n; char c; ull leftHash0=0, rightHash0=0; ull leftHash1=0, rightHash1=0; ull leftHash2=0, rightHash2=0; ull leftHash3=0, rightHash3=0; ull ck0=1; ull ck1=1; ull ck2=1; ull ck3=1; do {scanf("%c", &c);} while((c<'a') || ('z'<c)); do {//printf(":%c:\n", c); ull cc=c-'a'+1; rightHash0=(rightHash0*29+cc)%((1<<30)-1); leftHash0=(leftHash0+ck0*cc)%((1<<30)-1); ck0=(ck0*29)%((1<<30)-1); rightHash1=(rightHash1*31+cc)%999999937; leftHash1=(leftHash1+ck1*cc)%999999937; ck1=(ck1*31)%999999937; rightHash2=(rightHash2*421+cc)%999999677; leftHash2=(leftHash2+ck2*cc)%999999677; ck2=(ck2*421)%999999677; rightHash3=(rightHash3*37+cc)%1000000007; leftHash3=(leftHash3+ck3*cc)%1000000007; ck3=(ck3*37)%1000000007; if(scanf("%c", &c)!=1)break; } while(('a'<=c) & (c<='z')); if(leftHash0!=rightHash0 || leftHash1!=rightHash1 || leftHash2!=rightHash2 || leftHash3!=rightHash3){ printf("NIE\n"); return 0; } printf("TAK\n"); return 0; } |