#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int len = 3e5+5, mod = 1e9+7, base = 57;
int suf[len], has1[len], has2[len], po[len], lim[len], n, lef[len], rig[len];
int tmp[len], ran[len], cnt[len];
char str[len];
vector<int> vec[len];
vector<ii> st;
set<int> mys;
inline int add(int a, int b){
a += b;
if (a >= mod) a -= mod;
return a;
}
inline int sub(int a, int b){
a -= b;
if (a < 0) a += mod;
return a;
}
int mul(int a, int b){
return (a*1LL*b)%mod;
}
inline int val1(int l, int r){
l++, r++;
return sub(has1[r], mul(has1[l-1], po[r-l+1]));
}
inline int val2(int l, int r){
return (sub(has2[l], mul(has2[r+1], po[r-l+1])));
}
int lcp(int a, int b){
int l = 1, r = n-1-max(a, b)+1, ans = 0;
while (l <= r){
int mid = (l+r)/2;
if (val1(a, a+mid-1) == val1(b, b+mid-1))
ans = mid, l = mid+1;
else
r = mid-1;
}
return ans;
}
bool comp(int a, int b){
int c = lcp(a, b);
return (str[a+c] < str[b+c]);
}
int bs(int i, int t){
int l = 1, r = min(n-i-t, i+1), ans = 0;
while (l <= r){
int mid = (l+r)/2;
if (val1(i-mid+1, i+t+mid-1) == val2(i-mid+1, i+t+mid-1))
ans = 2*mid - (1-t), l = mid+1;
else
r = mid-1;
}
return ans;
}
void radix(int k){
for (int i = 0; i < max(n, 300); i++)
cnt[i] = 0;
for (int i = 0; i < n; i++)
cnt[ran[suf[i]]+1]++;
for (int i = 1; i <= max(n, 300); i++)
cnt[i] += cnt[i-1];
for (int i = 0; i < n; i++)
tmp[cnt[ran[suf[i]]]++] = suf[i];
for (int i = 0; i < n; i++)
suf[i] = tmp[i];
}
int main(){
scanf("%s", &str);
n = strlen(str);
str[n] = 0;
po[0] = 1;
for (int i = 1; i <= n; i++)
po[i] = mul(po[i-1], base);
for (int i = 1; i <= n; i++)
has1[i] = add(mul(has1[i-1], base), str[i-1]-'a');
for (int i = n-1; i >= 0; i--)
has2[i] = add(mul(has2[i+1], base), str[i]-'a');
for (int i = 0; i < n; i++)
suf[i] = i;
//sort(suf, suf+n, comp); // suffix array before :(
for (int i = 0; i < n; i++)
ran[i] = str[i];
for (int k = 1; k <= n; k*=2){
radix(k);
radix(0);
int ptr = -1;
for (int i = 0; i < n; i++){
if (i == 0 || ran[suf[i]] != ran[suf[i-1]] || (suf[i]+k<n?ran[suf[i]+k]:0) != (suf[i-1]+k<n?ran[suf[i-1]+k]:0))
tmp[suf[i]] = ++ptr;
else
tmp[suf[i]] = ptr;
}
for (int i = 0; i < n; i++)
ran[i] = tmp[i];
}
for (int i = 0; i < n; i++)
lim[i] = -1;
for (int i = 0; i < n-1; i++)
lim[suf[i]] = lcp(suf[i], suf[i+1]);
//for (int i = 0; i < n; i++)
// printf("%d ", suf[i]);
//printf("\n");
ll ans = 0;
for (int i = 0; i < n; i++){
int temp = bs(i, 0);
vec[i-temp/2].pb(temp);
ans = max(ans, (ll)temp);
//printf("i = %d, mx0 = %d\n", i, temp);
temp = bs(i, 1);
vec[i-temp/2+1].pb(temp);
ans = max(ans, (ll)temp);
//printf("i = %d, mx1 = %d\n", i, temp);
}
int k = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < vec[i].size(); j++)
mys.insert(vec[i][j]-k);
set<int>::iterator it = mys.upper_bound(lim[i]-k);
if (lim[i] != -1 && it != mys.begin()){
it = prev(it);
lim[i] = *it + k;
}
else
lim[i] = 0;
k-=2;
}
//for (int i = 0; i < n-1; i++)
// printf("%d ", lim[suf[i]]);
//printf("\n");
st.pb(mp(-1, -1));
for (int i = 0; i < n-1; i++){
while (lim[suf[i]] <= st.back().fi)
st.pop_back();
lef[i] = st.back().se;
st.pb(mp(lim[suf[i]], i));
}
st.clear(), st.pb(mp(-1, n-1));
for (int i = n-2; i >= 0; i--){
while (lim[suf[i]] <= st.back().fi)
st.pop_back();
rig[i] = st.back().se;
st.pb(mp(lim[suf[i]], i));
}
for (int i = 0; i < n-1; i++)
ans = max(ans, lim[suf[i]] * 1LL * (rig[i]-lef[i]));
printf("%lld\n", ans);
return 0;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:90:21: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
scanf("%s", &str);
~~~~^
palindrome.cpp:150:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec[i].size(); j++)
~~^~~~~~~~~~~~~~~
palindrome.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &str);
~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
7356 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7536 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
7536 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
7716 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7716 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7792 KB |
Output is correct |
| 4 |
Correct |
10 ms |
7940 KB |
Output is correct |
| 5 |
Correct |
10 ms |
7940 KB |
Output is correct |
| 6 |
Correct |
11 ms |
7940 KB |
Output is correct |
| 7 |
Correct |
9 ms |
7940 KB |
Output is correct |
| 8 |
Correct |
10 ms |
7940 KB |
Output is correct |
| 9 |
Correct |
10 ms |
7940 KB |
Output is correct |
| 10 |
Correct |
9 ms |
7940 KB |
Output is correct |
| 11 |
Correct |
11 ms |
7940 KB |
Output is correct |
| 12 |
Correct |
9 ms |
7940 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
9468 KB |
Output is correct |
| 2 |
Correct |
23 ms |
9592 KB |
Output is correct |
| 3 |
Correct |
23 ms |
9596 KB |
Output is correct |
| 4 |
Correct |
22 ms |
9596 KB |
Output is correct |
| 5 |
Incorrect |
22 ms |
9596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
220 ms |
25084 KB |
Output is correct |
| 2 |
Correct |
220 ms |
25084 KB |
Output is correct |
| 3 |
Correct |
197 ms |
25648 KB |
Output is correct |
| 4 |
Correct |
221 ms |
25648 KB |
Output is correct |
| 5 |
Incorrect |
178 ms |
25648 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
781 ms |
59568 KB |
Output is correct |
| 2 |
Correct |
732 ms |
59568 KB |
Output is correct |
| 3 |
Correct |
720 ms |
63268 KB |
Output is correct |
| 4 |
Correct |
736 ms |
63268 KB |
Output is correct |
| 5 |
Incorrect |
593 ms |
63268 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
