#include <bits/stdc++.h> using namespace std; int dlugosc, wynik; string wyraz, slowo; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> dlugosc; cin >> slowo; if(dlugosc==0) dlugosc=slowo.size(); wyraz+='#'; for(int i=1; i<=dlugosc; i++) { wyraz+=slowo[i-1]; } wyraz+='$'; int R[dlugosc]; int i=1; int t=0; R[0]=0; if(dlugosc%2==0) { while(i<=dlugosc) { while(wyraz[i-t]==wyraz[i+t+1]) { t++; } R[i]=t; int k=1; while(k<=t && R[i-k]!=R[i]-k) { R[i+k]=min(R[i-k], (R[i]-k)); k++; } t-=k; t=max(0, t); i+=k; } for(int i=0; i<dlugosc; i++) { wynik=max(wynik,R[i]); } if(wynik*2==dlugosc) { cout << "TAK" << endl; return 0; } else { cout << "NIE" << endl; return 0; } } else if(dlugosc%2!=0) { while(i<=dlugosc) { while(wyraz[i-t-1]==wyraz[i+t+1]) { t++; } R[i]=t; int k=1; while(k<=t && R[i-k]!=R[i]-k) { R[i+k]=min(R[i-k], (R[i]-k)); k++; } t=max(t-k, 0); i+=k; } for(int i=0; i<dlugosc; i++) { wynik=max(wynik,R[i]); } if(wynik*2+1==dlugosc) { cout << "TAK" << endl; return 0; } else { cout << "NIE" << endl; return 0; } } 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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #include <bits/stdc++.h> using namespace std; int dlugosc, wynik; string wyraz, slowo; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> dlugosc; cin >> slowo; if(dlugosc==0) dlugosc=slowo.size(); wyraz+='#'; for(int i=1; i<=dlugosc; i++) { wyraz+=slowo[i-1]; } wyraz+='$'; int R[dlugosc]; int i=1; int t=0; R[0]=0; if(dlugosc%2==0) { while(i<=dlugosc) { while(wyraz[i-t]==wyraz[i+t+1]) { t++; } R[i]=t; int k=1; while(k<=t && R[i-k]!=R[i]-k) { R[i+k]=min(R[i-k], (R[i]-k)); k++; } t-=k; t=max(0, t); i+=k; } for(int i=0; i<dlugosc; i++) { wynik=max(wynik,R[i]); } if(wynik*2==dlugosc) { cout << "TAK" << endl; return 0; } else { cout << "NIE" << endl; return 0; } } else if(dlugosc%2!=0) { while(i<=dlugosc) { while(wyraz[i-t-1]==wyraz[i+t+1]) { t++; } R[i]=t; int k=1; while(k<=t && R[i-k]!=R[i]-k) { R[i+k]=min(R[i-k], (R[i]-k)); k++; } t=max(t-k, 0); i+=k; } for(int i=0; i<dlugosc; i++) { wynik=max(wynik,R[i]); } if(wynik*2+1==dlugosc) { cout << "TAK" << endl; return 0; } else { cout << "NIE" << endl; return 0; } } return 0; } |