/** Im the best because i work as hard as i possibly can **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl "\n"
const int N = 3e5 + 10;
const ll mod = 884577481;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 20;
const ll base = 609859;
string s;
char C[N];
ll PW, n, T, lcp[N], tmp[N], Cnt[N], SA[N], rnk[N], seg[N << 2];
ll pw[N], hshL[N], hshR[N];
inline void BuildSuffixArray(const string &s){
assert((s[0] == '$') && (n + 1 == (int)s.size()));
iota(SA + 1, SA + n + 1, 1), SA[0] = n + 1;
for(int i = 1; i <= n; i ++) rnk[i] = s[i];
int _Max = 'z', p = 1, k;
for(PW = 0; p < n; PW ++){
k = ((1LL << PW) >> 1), p = 1;
for(int i = n - k + 1; i <= n; i ++){
tmp[p ++] = i;
}
for(int i = 1; i <= n; i ++){
if(SA[i] > k) tmp[p ++] = SA[i] - k;
}
for(int i = 0; i <= _Max; i ++) Cnt[i] = 0;
for(int i = 1; i <= n; i ++) Cnt[rnk[i]] ++;
for(int i = 1; i <= _Max; i ++){
Cnt[i] += Cnt[i - 1];
}
for(int i = n; i; i --){
SA[Cnt[rnk[tmp[i]]] --] = tmp[i];
}
swap(rnk, tmp);
rnk[SA[1]] = p = 1;
for(int i = 2; i <= n; i ++){
if(tmp[SA[i - 1]] != tmp[SA[i]] || SA[i - 1] + k > n || tmp[SA[i - 1] + k] != tmp[SA[i] + k]){
p ++;
}
rnk[SA[i]] = p;
}
_Max = p;
}
SA[0] = n + 1;
}
inline void BuildLcpTable(const string &s){
assert((s[0] == '$') && (n + 1 == (int)s.size()));
for(int i = 1, k = 0; i <= n; i ++){
if(rnk[i] == n) continue;
if(k) k --;
while(s[i + k] == s[SA[rnk[i] + 1] + k]){
k ++;
}
lcp[rnk[i] + 1] = k;
}
}
inline ll baze(int l, int r)
{
return (hshL[r] - (hshL[l - 1] * pw[r - l + 1] % mod) + mod) % mod;
}
inline ll baze2(int l, int r)
{
return (hshR[l] - (hshR[r + 1] * pw[r - l + 1] % mod) + mod) % mod;
}
void build(int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
seg[v] = lcp[tl];
return;
}
int mid = (tl + tr) >> 1;
build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
seg[v] = min(seg[v << 1], seg[v << 1 | 1]);
}
int find_nxt(int p, int x, int v = 1, int tl = 1, int tr = n)
{
if(p > n) return n + 1;
if(tr < p) return -1;
if(seg[v] >= x)
{
if(tr == n) return n + 1;
return -1;
}
if(tl == tr) return tl;
int mid = (tl + tr) >> 1;
int cu = find_nxt(p, x, v << 1, tl, mid);
if(cu == -1) cu = find_nxt(p, x, v << 1 | 1, mid + 1, tr);
return cu;
}
int find_prv(int p, int x, int v = 1, int tl = 1, int tr = n)
{
if(tl > p) return -1;
if(seg[v] >= x)
{
if(tl == 1) return 0;
return -1;
}
if(tl == tr) return tl;
int mid = (tl + tr) >> 1;
int cu = find_prv(p, x, v << 1 | 1, mid + 1, tr);
if(cu == -1) cu = find_prv(p, x, v << 1, tl, mid);
return cu;
}
ll calc(int l, int r)
{
int sz = r - l + 1, id = rnk[l];
int L = find_prv(id, sz);
int R = find_nxt(id + 1, sz);
return R - L;
}
int main()
{
scanf("%s", C);
n = strlen(C);
s = C;
s = "$" + s;
BuildSuffixArray(s);
BuildLcpTable(s);
build();
ll tot = 0;
for(ll i = 1; i <= n; i ++)
{
int d = 0, up = min(i - 1, n - i) + 1;
while(up - d > 1)
{
int mid = (up + d) >> 1;
if(baze(i, i + mid) == baze2(i - mid, i)) d = mid;
else up = mid;
}
tot = max(tot, calc(i - d, i + d) * (2 * d + 1));
}
for(ll i = 1; i < n; i ++)
{
if(s[i] != s[i + 1]) continue;
int d = 0, up = min(i - 1, n - i - 1) + 1;
while(up - d > 1)
{
int mid = (up + d) >> 1;
if(baze(i + 1, i + 1 + mid) == baze2(i - mid, i)) d = mid;
else up = mid;
}
tot = max(tot, calc(i - d, i + d + 1) * (2 * d + 2));
}
printf("%lld", tot);
return 0;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
142 | scanf("%s", C);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 9 |
Correct |
6 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5100 KB |
Output is correct |
| 11 |
Incorrect |
6 ms |
5100 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
9 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5100 KB |
Output is correct |
| 7 |
Incorrect |
8 ms |
5100 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
5612 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
5612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
9580 KB |
Output is correct |
| 2 |
Correct |
77 ms |
9580 KB |
Output is correct |
| 3 |
Correct |
112 ms |
9452 KB |
Output is correct |
| 4 |
Correct |
126 ms |
9580 KB |
Output is correct |
| 5 |
Incorrect |
102 ms |
9836 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
272 ms |
20580 KB |
Output is correct |
| 2 |
Incorrect |
231 ms |
20676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
