#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5, sigma = 26;
int len[maxn], link[maxn], to[maxn][sigma];
int slink[maxn], diff[maxn], series_ans[maxn];
int sz, last, n;
char s[maxn];
void init()
{
n = 0;
s[n++] = -1;
link[0] = 1;
len[1] = -1;
sz = 2;
}
int get_link(int v)
{
while(s[n - len[v] - 2] != s[n - 1]) v = link[v];
return v;
}
void add_letter(char c)
{
//cout << "ADD_LETTER " << n << endl;
s[n++] = c -= 'a';
last = get_link(last);
if(!to[last][c])
{
len[sz] = len[last] + 2;
link[sz] = to[get_link(link[last])][c];
diff[sz] = len[sz] - len[link[sz]];
if(diff[sz] == diff[link[sz]])
slink[sz] = slink[link[sz]];
else
slink[sz] = link[sz];
to[last][c] = sz++;
}
last = to[last][c];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
for (int testcase = 0; testcase < T; testcase++){
init();
string t;
cin >> t;
string s;
for (int i = 0; i < t.size() / 2; i++){
s += t[i];
s += t[t.size() - i - 1];
}
if (t.size() % 2 == 1){
s += t[t.size() / 2];
}
int N = s.size();
int ans[N + 1];
memset(ans, 0, sizeof(ans));
ans[0] = 0;
int res = 0;
for(int i = 1; i <= N; i++)
{
add_letter(s[i - 1]);
//cout << "FOR LOOP " << n << endl;
for(int v = last; len[v] > 0; v = link[v])
if (len[v] % 2 == 0)
ans[i] = max(ans[i], ans[i - len[v]] + 2);
if (i != n){
res = max(res, ans[i] + 1);
}
else{
res = max(res, ans[i]);
}
}
cout << res << endl;
}
return 0;
}
Compilation message
palindromic.cpp: In function 'void add_letter(char)':
palindromic.cpp:31:19: warning: array subscript has type 'char' [-Wchar-subscripts]
if(!to[last][c])
^
palindromic.cpp:34:46: warning: array subscript has type 'char' [-Wchar-subscripts]
link[sz] = to[get_link(link[last])][c];
^
palindromic.cpp:40:19: warning: array subscript has type 'char' [-Wchar-subscripts]
to[last][c] = sz++;
^
palindromic.cpp:42:22: warning: array subscript has type 'char' [-Wchar-subscripts]
last = to[last][c];
^
palindromic.cpp: In function 'int main()':
palindromic.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < t.size() / 2; i++){
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10010 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10010 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10010 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10010 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
