#include <iostream> const int N = 3; typedef long long LL; using namespace std; LL modulo[N] = {980232353, 1481906267, 920559389};//,1724491669,1018023557,1461449827}; LL podstawa[N] ={29,31,29};//,39,30,37}; LL pot[N] = {}; LL haszL[N] ={}; LL haszP[N] = {}; void updateL(LL& ha, LL mod, LL pods, char c) { ha = (ha*pods + (c-'a' + 1))%mod; } void updateP(LL& ha, LL mod, LL pods, LL& pot, char c) { ha= (ha + pot*(c-'a'+1))%mod; pot = (pods * pot) %mod; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); for(int i = 0;i<N;++i) pot[i] = 1; int n = 20000000; cin>>n; char c; while(cin>>c) { //c = (c-'a' + 1)%26+'a'; for(int i = 0;i < N; ++i) { updateL(haszL[i], modulo[i], podstawa[i], c); updateP(haszP[i], modulo[i], podstawa[i], pot[i], c); } } for(int i = 0; i < N; ++i) { if(haszP[i] != haszL[i]) { cout<<"NIE\n"; return 0; } } cout<<"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 60 61 | #include <iostream> const int N = 3; typedef long long LL; using namespace std; LL modulo[N] = {980232353, 1481906267, 920559389};//,1724491669,1018023557,1461449827}; LL podstawa[N] ={29,31,29};//,39,30,37}; LL pot[N] = {}; LL haszL[N] ={}; LL haszP[N] = {}; void updateL(LL& ha, LL mod, LL pods, char c) { ha = (ha*pods + (c-'a' + 1))%mod; } void updateP(LL& ha, LL mod, LL pods, LL& pot, char c) { ha= (ha + pot*(c-'a'+1))%mod; pot = (pods * pot) %mod; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); for(int i = 0;i<N;++i) pot[i] = 1; int n = 20000000; cin>>n; char c; while(cin>>c) { //c = (c-'a' + 1)%26+'a'; for(int i = 0;i < N; ++i) { updateL(haszL[i], modulo[i], podstawa[i], c); updateP(haszP[i], modulo[i], podstawa[i], pot[i], c); } } for(int i = 0; i < N; ++i) { if(haszP[i] != haszL[i]) { cout<<"NIE\n"; return 0; } } cout<<"TAK\n"; return 0; } |