#include <iostream>
#include <ios>
#include <algorithm>
#include <string>
#include <vector>
#include <array>
#include <stack>
const int MAX_N = 600006;
std::vector<int> make_sa(const std::string& s)
{
int n = s.length();
std::vector<int> sa(n), g(n+1), ng(n+1);
for(int i=0;i<n;i++)
{
sa[i] = i;
g[i] = s[i];
}
g[n] = 0;
int lim = std::max(128, n+1);
for(int t=1;t<s.length();t<<=1)
{
auto cmp = [&] (int a, int b) {
return g[a] != g[b] ? g[a] < g[b] : g[a+t] < g[b+t];
};
std::vector<int> cnt(lim), ind(lim+1);
for(int i=0;i<n;i++) cnt[g[std::min(i+t, n)]]++;
for(int i=1;i<lim;i++) cnt[i] += cnt[i-1];
for(int i=n-1;i>=0;i--) ind[--cnt[g[std::min(i+t, n)]]] = i;
for(int i=0;i<lim;i++) cnt[i] = 0;
for(int i=0;i<n;i++) cnt[g[i]]++; // same as cnt[g[ind[i]]]++
for(int i=1;i<lim;i++) cnt[i] += cnt[i-1];
for(int i=n-1;i>=0;i--) sa[--cnt[g[ind[i]]]] = ind[i];
ng[sa[0]] = 1;
for(int i=1;i<n;i++)
{
ng[sa[i]] = ng[sa[i-1]];
if(cmp(sa[i-1], sa[i])) ng[sa[i]]++;
}
g = ng;
}
return sa;
}
std::vector<int> make_lcp(const std::string& s, const std::vector<int>& sa)
{
int n = s.length();
std::vector<int> lcp(n+1);
std::vector<int> rank(n);
for(int i=0;i<n;i++)
rank[sa[i]] = i;
int len = 0;
for(int i=0;i<n;i++)
{
if(rank[i])
{
int j = sa[rank[i]-1];
int len_cap = n - std::max(i,j);
while(len < len_cap && s[i+len] == s[j+len]) len++;
lcp[rank[i]-1] = len;
}
if(len) len--;
}
return lcp;
}
long long int get_max_area(const std::vector<int>& v)
{
std::stack<int> sh, sx;
int n = v.size();
long long int ans = 0;
for(int i=0;i<=n;i++)
{
int val = i < n ? v[i] : 0;
int len = 0;
int last_x = i;
while(!sh.empty() && sh.top() >= val)
{
ans = std::max(ans, 1LL * sh.top() * (i-sx.top()+1));
last_x = sx.top();
sh.pop();
sx.pop();
}
sh.push(val);
sx.push(last_x);
}
return ans;
}
std::string make_appended_str(const std::string& s)
{
std::vector<char> v;
for(int i=0;i<=s.length();i++)
{
v.push_back('_');
if(i != s.length()) v.push_back(s[i]);
}
return std::string(v.begin(), v.end());
}
std::vector<int> manacher(const std::string& s)
{
std::vector<int> ret(s.length());
int r = -1;
int p = -1;
for(int i=0;i<s.length();i++)
{
if(i <= r) ret[i] = std::min(r-i, ret[2*p-i]);
while(ret[i]+1 <= i && i+ret[i]+1 < s.length() &&
s[i-ret[i]-1] == s[i+ret[i]+1])
ret[i]++;
if(i + ret[i] > r)
r = i + ret[i], p = i;
}
return ret;
}
int spl[MAX_N+1];
int sp[20][MAX_N];
void set_sp(std::vector<int>& lcp)
{
int n = lcp.size();
for(int j=0;j<n;j++)
sp[0][j] = lcp[j];
for(int i=1;i<20;i++)
{
for(int j=1;j<=(1<<i);j++)
{
if((1<<i)+j <= MAX_N) spl[(1<<i)+j] = i;
}
}
for(int i=0;i<19;i++)
{
for(int j=0;j<n;j++)
{
sp[i+1][j] = std::min(sp[i][j], sp[i][std::min(j+(1<<i), n-1)]);
}
}
}
long long int solve(std::string& s)
{
std::string s_ = make_appended_str(s);
std::vector<int> sa = make_sa(s_);
std::vector<int> rank(sa.size());
for(int i=0;i<sa.size();i++)
rank[sa[i]] = i;
std::vector<int> lcp = make_lcp(s_, sa);
std::vector<int> ma = manacher(s_);
set_sp(lcp);
auto lcp_val = [&] (int x, int y)
{
x = rank[x];
y = rank[y];
if(x>y) std::swap(x,y);
int len = y-x;
int res = std::min(sp[spl[len]][x], sp[spl[len]][y-(1<<spl[len])]);
return res;
};
auto cmp = [&] (int x, int y)
{
int len = y-x+ 1;
int clen = std::min({lcp_val(x,y), ma[x]+1, ma[y]+1});
char chx = clen != ma[x]+1 && x+clen < s_.length() ? s_[x+clen] : 0;
char chy = clen != ma[y]+1 && y+clen < s_.length() ? s_[y+clen] : 0;
return (chx != chy ? chx < chy : x<y);
};
std::vector<int> ord(s_.length());
for(int i=0;i<s_.length();i++)
ord[i] = i;
std::sort(ord.begin(), ord.end(), cmp);
std::vector<int> lcp_palin;
for(int i=1;i<ord.size();i++)
{
int v = std::min({
ma[ord[i-1]],
ma[ord[i]],
lcp_val(ord[i-1], ord[i])-1});
lcp_palin.push_back(std::max(v,0));
}
return get_max_area(lcp_palin);
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::string s;
std::cin >> s;
std::cout << std::max(solve(s), (long long int)s.length());
}
Compilation message
palindrome.cpp: In function 'std::vector<int> make_sa(const string&)':
palindrome.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int t=1;t<s.length();t<<=1)
~^~~~~~~~~~~
palindrome.cpp: In function 'long long int get_max_area(const std::vector<int>&)':
palindrome.cpp:83:13: warning: unused variable 'len' [-Wunused-variable]
int len = 0;
^~~
palindrome.cpp: In function 'std::__cxx11::string make_appended_str(const string&)':
palindrome.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<=s.length();i++)
~^~~~~~~~~~~~
palindrome.cpp:103:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i != s.length()) v.push_back(s[i]);
~~^~~~~~~~~~~~~
palindrome.cpp: In function 'std::vector<int> manacher(const string&)':
palindrome.cpp:112:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s.length();i++)
~^~~~~~~~~~~
palindrome.cpp:115:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ret[i]+1 <= i && i+ret[i]+1 < s.length() &&
~~~~~~~~~~~^~~~~~~~~~~~
palindrome.cpp: In function 'long long int solve(std::__cxx11::string&)':
palindrome.cpp:152:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sa.size();i++)
~^~~~~~~~~~
palindrome.cpp: In lambda function:
palindrome.cpp:171:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
char chx = clen != ma[x]+1 && x+clen < s_.length() ? s_[x+clen] : 0;
~~~~~~~^~~~~~~~~~~~~
palindrome.cpp:172:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
char chy = clen != ma[y]+1 && y+clen < s_.length() ? s_[y+clen] : 0;
~~~~~~~^~~~~~~~~~~~~
palindrome.cpp:169:13: warning: unused variable 'len' [-Wunused-variable]
int len = y-x+ 1;
^~~
palindrome.cpp: In function 'long long int solve(std::__cxx11::string&)':
palindrome.cpp:176:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s_.length();i++)
~^~~~~~~~~~~~
palindrome.cpp:182:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<ord.size();i++)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2924 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2924 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2924 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
2988 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3172 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3352 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3352 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3352 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3352 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3352 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
3352 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
5248 KB |
Output is correct |
| 2 |
Correct |
17 ms |
5284 KB |
Output is correct |
| 3 |
Correct |
21 ms |
5288 KB |
Output is correct |
| 4 |
Correct |
19 ms |
5288 KB |
Output is correct |
| 5 |
Incorrect |
21 ms |
5288 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
24788 KB |
Output is correct |
| 2 |
Correct |
181 ms |
24788 KB |
Output is correct |
| 3 |
Correct |
162 ms |
24916 KB |
Output is correct |
| 4 |
Correct |
195 ms |
24916 KB |
Output is correct |
| 5 |
Incorrect |
364 ms |
24916 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
573 ms |
69132 KB |
Output is correct |
| 2 |
Correct |
605 ms |
69132 KB |
Output is correct |
| 3 |
Correct |
507 ms |
69160 KB |
Output is correct |
| 4 |
Correct |
624 ms |
69160 KB |
Output is correct |
| 5 |
Execution timed out |
1078 ms |
69160 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
