#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define hell 1000000007
#define endl '\n'
using namespace std;
const int MAXN=1000005;
string s;
struct PalindromicTree{
int N,cur;
vector<map<int,int>> next;
vector<int> link,start,len,diff,slink;
PalindromicTree(): N(0),cur(0){
node();
len[0]=-1;
node();
}
int node(){
next.emplace_back();
link.emplace_back(0);
start.emplace_back(0);
len.emplace_back(0);
diff.emplace_back(0);
slink.emplace_back(0);
return N++;
}
void add_letter(int idx){
//cout << s[idx] << endl;
while(true){
if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx])
break;
cur=link[cur];
}
if(next[cur].find(s[idx])!=next[cur].end()){
cur=next[cur][s[idx]];
return;
}
node();
next[cur][s[idx]]=N-1;
len[N-1]=len[cur]+2;
start[N-1]=idx-len[N-1]+1;
if(len[N-1]==1){
link[N-1]=diff[N-1]=slink[N-1]=1;
cur=N-1;
return;
}
while(true){
cur=link[cur];
if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx])
break;
}
link[N-1]=next[cur][s[idx]];
diff[N-1]=len[N-1]-len[link[N-1]];
if(diff[N-1]==diff[link[N-1]])
slink[N-1]=slink[link[N-1]];
else
slink[N-1]=link[N-1];
cur=N-1;
}
};
ll dp[MAXN],sans[MAXN];
int main()
{
int T; cin >> T;
for (int testcase = 0; testcase < T; testcase++){
string str;
cin>>str;
//cout << str << endl;
PalindromicTree pt;
int i,cur;
s.clear();
for(i=0;i<sz(str)/2;i++){
s.pb(str[i]);
s.pb(str[sz(str)-i-1]);
}
if (sz(str) % 2){
s.pb(str[sz(str)/2]);
}
//cout << s.size() << endl;
dp[0]=0;
int res = 1;
for(i=1;i<=sz(s);i++){
dp[i] = -hell;
pt.add_letter(i-1);
//cout << i << ' ' << dp[i] << ' ' << pt.cur << endl;
int cnt = 0;
for(cur=pt.cur;cur>1;cur=pt.slink[cur]){
if (pt.len[cur] % 2 == 0){
dp[i] = max(dp[i], dp[i - pt.len[cur]] + 2);
}
cnt++;
if (cnt < 300) break;
}
int cur = dp[i];
if (i != sz(s)) cur++;
if (cur > res) res = cur;
}
cout << res << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
