#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
const int sigma = 26;
struct Node
{
int start, end;
int length;
int insertEdg[26];
int suffixEdg;
int cnt = 0;
};
Node root1, root2;
Node tree[MAXN];
int currNode;
string s;
int ptr;
void init(){
root1.length = -1;
root1.suffixEdg = 1;
root2.length = 0;
root2.suffixEdg = 1;
tree[1] = root1;
tree[2] = root2;
ptr = 2;
currNode = 1;
}
void insert(int idx)
{
//STEP 1//
/* search for Node X such that s[idx] X S[idx]
is maximum palindrome ending at position idx
iterate down the suffix link of currNode to
find X */
int tmp = currNode;
while (true)
{
int curLength = tree[tmp].length;
if (idx - curLength >= 1 and s[idx] == s[idx-curLength-1])
break;
tmp = tree[tmp].suffixEdg;
}
/* Now we have found X ....
* X = string at Node tmp
* Check : if s[idx] X s[idx] already exists or not*/
if(tree[tmp].insertEdg[s[idx]-'a'] != 0)
{
// s[idx] X s[idx] already exists in the tree
currNode = tree[tmp].insertEdg[s[idx]-'a'];
return;
}
// creating new Node
ptr++;
// making new Node as child of X with
// weight as s[idx]
tree[tmp].insertEdg[s[idx]-'a'] = ptr;
// calculating length of new Node
tree[ptr].length = tree[tmp].length + 2;
// updating end point for new Node
tree[ptr].end = idx;
// updating the start for new Node
tree[ptr].start = idx - tree[ptr].length + 1;
//STEP 2//
/* Setting the suffix edge for the newly created
Node tree[ptr]. Finding some String Y such that
s[idx] + Y + s[idx] is longest possible
palindromic suffix for newly created Node.*/
tmp = tree[tmp].suffixEdg;
// making new Node as current Node
currNode = ptr;
if (tree[currNode].length == 1)
{
// if new palindrome's length is 1
// making its suffix link to be null string
tree[currNode].suffixEdg = 2;
return;
}
while (true)
{
int curLength = tree[tmp].length;
if (idx-curLength >= 1 and s[idx] == s[idx-curLength-1])
break;
tmp = tree[tmp].suffixEdg;
}
// Now we have found string Y
// linking current Nodes suffix link with s[idx]+Y+s[idx]
tree[currNode].suffixEdg = tree[tmp].insertEdg[s[idx]-'a'];
}
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;
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++)
{
insert(i - 1);
//cout << "FOR LOOP " << n << endl;
for(int v = currNode; tree[v].length > 0; v = tree[v].suffixEdg){
if (tree[v].length % 2 == 0)
ans[i] = max(ans[i], ans[i - tree[v].length] + 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 'int main()':
palindromic.cpp:121: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 |
10045 ms |
121720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10045 ms |
121720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10045 ms |
121720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10045 ms |
121720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
