#include <bits/stdc++.h>
#define DIM 1000010
#define MOD 1000000007
using namespace std;
int t,n,i,j;
char v[DIM];
vector <int> poz[30];
int cautare_binara (vector <int> v, int poz){
/// prima pozitie mai mare decat poz
int st = 0, dr = v.size()-1, sol = -1;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[mid] > poz){
dr = mid-1;
sol = mid;
} else st = mid+1;
}
if (sol == -1)
return n+1;
return sol;
}
int main (){
//ifstream fin ("date.in");
//ofstream fout ("date.out");
cin>>t;
for (;t--;){
for (int i=0;i<=26;++i)
poz[i].clear();
cin>>v+1;
n = strlen (v+1);
int st = 1, dr = n, sol = 0;
int st_ant = 0, dr_ant = n+1, nr = 0;
long long prf = 0, suf = 0, p = 1;
while (st < dr){
if (v[st] == v[dr]){
sol += 2;
++st, --dr;
continue;
}
prf = (prf*27 + v[st] - '0')%MOD;
suf = (suf + p*(v[dr] - '0'))%MOD;
p = (p*27)%MOD;
nr++;
if (prf == suf){
/// trb sa mai testez odata daca sunt egale
int ok = 1;
for (int i=st_ant+1,j=dr;i<=st,j<dr_ant;i++,j++){
if (v[i] != v[j]){
ok = 0;
break;
}}
if (ok){ /// sunt egale
sol += 2;
prf = 0, suf = 0, p = 1, nr = 0;
st_ant = st, dr_ant = dr;
}
}
st++, dr--;
}
if (st == dr || nr)
sol++;
cout<<sol<<"\n";
/* for (i=1;i<=n;++i){
// hash[i] = (hash[i-1]*27 + v[i]-'a')%MOD;
poz[v[i]-'a'].push_back(i);
}
int st = 1, dr = n, sol = 0;
while (st < dr){
if (v[st] == v[dr]){
sol += 2;
++st, --dr;
continue;
}
/// caut binar prima aparite a lui v[dr] dupa st
int x = st;
int val = cautare_binara (poz[v[dr]-'a'],x);
for (;;){
if (val < poz[v[dr]-'a'].size())
x = poz[v[dr]-'a'][val];
else x = n+1;
int lg = x-st+1;
if (x >= dr-lg+1){
/// nu am gasit nimic deci trebuie sa l iau pe tot
sol++;
st = dr+1;
break;
}
int ok = 1;
for (int j=st,t=dr-lg+1;j<=x;++j,++t){
if (v[j] != v[t]){
ok = 0;
break;
}}
if (ok){
sol += 2;
st += lg, dr -= lg;
break;
}
++val;
}
}
if (st == dr)
++sol;
cout<<sol<<"\n";*/
}
return 0;
}
Compilation message
palindromic.cpp: In function 'int main()':
palindromic.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
cin>>v+1;
~^~
palindromic.cpp:50:43: warning: left operand of comma operator has no effect [-Wunused-value]
for (int i=st_ant+1,j=dr;i<=st,j<dr_ant;i++,j++){
~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
