#include <bits/stdc++.h>
#include <random>
#include <ext/rope>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
const int alf = 26;
const int maxn = 2*300005;
struct sf
{
sf(){len = 0;link = 0;l = 0;c = 0;};
int go[alf];
int len,link;
int l;
int64_t c;
};
vector<sf> sa(maxn);
void init()
{
sa[0].link = -1;
sa[0].len = 0;
sa[0].c = 0;
sa[0].l = -1;
for(int i = 0;i < sa.size();++i)
{
for(int j = 0;j < alf;++j)
sa[i].go[j] = -1;
}
return ;
}
int last = 0,sz = 1;
void add(char c)
{
int x = c-'a';
int cur = sz++;
sa[cur].len = sa[last].len+1;
sa[cur].l = 0;
sa[cur].c = 1;
int p = last;
while(p != -1 && sa[p].go[x] == -1)
{
sa[p].go[x] = cur;
p = sa[p].link;
}
// cout << p << ' ';
if(p == -1)
{
sa[cur].link = 0;
}
else
{
int q = sa[p].go[x];
if(sa[p].len == sa[q].len-1)
{
sa[cur].link = q;
}
else
{
int clone = sz++;
sa[clone].len = sa[p].len + 1;
sa[clone].link = sa[q].link;
for(int i = 0;i < alf;++i)
sa[clone].go[i] = sa[q].go[i];
sa[clone].c = 0;
sa[clone].l = sa[q].l + sa[q].len - sa[p].len - 1;
sa[q].link = sa[cur].link = clone;
int cp = p;
while(sa[cp].go[x] == q)
{
sa[cp].go[x] = clone;
cp = sa[cp].link;
}
}
}
last = cur;
return ;
}
vector<int64_t> phash(maxn/2),shash(maxn/2),st(maxn/2);
const int64_t mod = int64_t(1e9)+7,p = 101;
bool qp(int64_t l,int64_t r)
{
// cout << shash[l] << ' ' << ((shash[r+1]*(st[r-l+1]))%mod) << "\n";
if((phash[r+1]-((phash[l]*(st[r-l+1]))%mod)+mod)%mod == (shash[l]-((shash[r+1]*(st[r-l+1]))%mod)+mod)%mod)
return true;
else
return false;
}
struct ev
{
ev(){t =0;c = 0;oc = 0;l = 0;};
ev(int64_t _t,bool _c,int64_t _oc,int64_t _l){t =_t;c = _c;oc = _oc;l = _l;};
int64_t t;
bool c;
int64_t oc;
int64_t l;
bool operator <(const ev& other)const
{
if(t != other.t)
return t < other.t;
if(c == other.c)
return oc < other.oc;
else
{
if(c == 0)
{
if(oc == 0)
return 1;
else
return 0;
}
else
{
if(other.oc == 0)
return 0;
else
return 1;
}
}
}
};
int main()
{
st[0] = 1;
for(int i =1;i < maxn;++i)
{
st[i] = (p*st[i-1])%mod;
}
string s;
cin >> s;
int n = s.size();
init();
for(int i = 0;i < s.size();++i)
{
// cout << 1;
add(s[i]);
}
vector<pair<int,int>> tr;
for(int i = 1;i < sz;++i)
{
tr.push_back({sa[i].len,i});
}
sort(tr.rbegin(),tr.rend());
for(int i = 0;i < sz-1;++i)
{
sa[sa[tr[i].second].link].c += sa[tr[i].second].c;
}
// cout << 1;
int64_t thash = 0;
phash[0] = thash;
for(int i = 0;i < s.size();++i)
{
thash *= p;
thash += s[i];
thash = thash%mod;
phash[i+1] = thash;
}
thash = 0;
shash[n] = thash;
for(int i = int(s.size())-1;i >= 0;--i)
{
thash *= p;
thash += s[i];
thash = thash%mod;
shash[i] = thash;
}
vector<ev> lg;
for(int i = 1;i < sz;++i)
{
// cout << sa[i].link << ' ' << sa[i].l << ' ' << sa[i].len << ' ' << sa[i].c << "\n";
lg.push_back(ev(sa[i].l + sa[i].len - 1,1,sa[i].c,sa[i].l));
}
for(int i = 0;i < n;++i)
{
int l = max(0,i-(n-i)+1),r = i;
while(l < r)
{
int m = (l+r)/2;
if(qp(m,2*i-m))
r = m;
else
l = m+1;
}
//cout << l << ' ' << i << "\n";
lg.push_back(ev(i,0,0,2*i));
lg.push_back(ev(2*i-l,0,1,2*i));
}
for(int i = 1;i < n;++i)
{
int l = max(1,i-(n-i)+1),r = i+1;
while(l < r)
{
int m = (l+r)/2;
if(qp(m-1,2*i-m))
r = m;
else
l = m+1;
}
//cout << l << ' ' << i << "\n";
if(l <= i)
{
lg.push_back(ev(i,0,0,2*i-1));
lg.push_back(ev(2*i-l,0,1,2*i-1));
}
}
sort(lg.begin(),lg.end());
int64_t ans = 0;
set<int> ss;
for(int i = 0;i < lg.size();++i)
{
ev x = lg[i];
if(x.c == 0)
{
if(x.oc == 0)
{
ss.insert(x.l);
}
else
ss.erase(x.l);
}
else
{
auto it = ss.lower_bound((x.l+x.t));
int64_t xx = (*it);
// cout << xx << ' ' << x.l << ' ' << x.t << "\n";
if(xx%2 == 0)
ans = max(ans,((x.t-(xx/2))*2+1)*(x.oc));
else
ans = max(ans,((x.t-(xx/2))*2)*(x.oc));
}
}
cout << ans;
return 0;
}
Compilation message
palindrome.cpp: In function 'void init()':
palindrome.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sf>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 0;i < sa.size();++i)
| ~~^~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:151:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i = 0;i < s.size();++i)
| ~~^~~~~~~~~~
palindrome.cpp:169:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for(int i = 0;i < s.size();++i)
| ~~^~~~~~~~~~
palindrome.cpp:229:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ev>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
229 | for(int i = 0;i < lg.size();++i)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
139 ms |
131072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
132 ms |
131072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
133 ms |
131072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
218 ms |
131072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
418 ms |
131072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
