#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int, int>
#define iii pair<ii, int>
#define mp make_pair
#define eb emplace_back
#define vi vector<int>
#define vii vector<ii>
#define viii vector<iii>
#define fi first
#define se second
#define xx fi.fi
#define yy fi.se
#define zz se
int n, mhash[600005], rnk[600005], sa[600005], lcp[600005], even[600006], odd[600005], h[600005], ans;
stack<int> st;
string s;
int f(int a, int b, int c)
{
assert(a<=1e6 and b<=1e6);
return a*(int)1e9+b*(int)50+c;
}
void build(int len, int N)
{
if(len==1)
{
for(int i=1; i+len-1<=N; i++)
{
mhash[i] = s[i] - 0;
}
}
else
{
map<int, int> M;
int hlf = len>>1;
build(hlf, N);
for(int i=1; i+len-1<=N; i++)
{
mhash[i] = f(mhash[i], mhash[i+hlf], (len&1? s[i+len-1] - 0: 0));
M[mhash[i]] = 0;
}
int curp = 0;
for(auto& x: M)
{
x.se = ++curp;
}
for(int i=1; i+len-1<=N; i++)
{
mhash[i] = M[mhash[i]];
}
}
}
bool cmp(int a, int b)
{
return mhash[a]<mhash[b];
}
signed main()
{
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>s; n = s.length();
s = '$'+s+'$'+s;
build(n, n);
for(int i=1; i<=n; i++)
{
sa[i] = i;
}
sort(sa+1, sa+n+1, cmp);
for(int i=1; i<=n; i++)
{
rnk[sa[i]] = i;
}
int curl = 0;
for(int i=1; i<=n; i++)
{
if(rnk[i]==n)
{
lcp[rnk[i]] = 0;
continue;
}
int j = sa[rnk[i]+1];
while(s[i+curl]==s[j+curl])
{
curl++;
}
lcp[rnk[i]] = curl;
if(curl) curl--;
}
int l = 0, r = 0;
for(int i=1; i<=n; i++)
{
if(l<=i and i<=r)
{
odd[i] = odd[l+r-i];
}
while(i-odd[i]>=1 and i+odd[i]<=n and s[i-odd[i]]==s[i+odd[i]])
{
odd[i]++;
}
if(odd[i] and r<i+odd[i]-1)
{
r = i+odd[i]-1;
l = i-odd[i]+1;
}
cout<<odd[i]<<endl;
}
l = 0, r = 0;
for(int i=2; i<=n; i++)
{
if(l<=i-1 and i<=r)
{
even[i] = even[l+r-i+1];
}
while(i-1-even[i]>=1 and i+even[i]<=n and s[i-1-even[i]] == s[i+even[i]]) even[i]++;
if(even[i] and r<i+even[i]-1)
{
r = i+even[i]-1;
l = i-even[i];
}
cout<<even[i]<<endl;
}
h[0] = -1;
for(int i=1; i<=n; i++)
{
h[2*i-1] = odd[i];
h[2*i] = lcp[i];
}
for(int i=0; i<=2*n; i++)
{
while(!st.empty() and h[st.top()]>=h[i])
{
int temp = st.top(); st.pop();
if(temp&1) ans = max(ans, (2*h[temp]-1)*((i%2==1? i-1: i) - (st.top()%2==1? st.top()+1: st.top()))/2);
}
st.push(i);
}
st = stack<int>();
for(int i=1; i<=n; i++)
{
h[2*i-1] = even[i];
h[2*i] = lcp[i];
}
for(int i=0; i<=2*n; i++)
{
while(!st.empty() and h[st.top()]>=h[i])
{
int temp = st.top(); st.pop();
if(temp&1) ans = max(ans, 2*h[temp]*((i%2==1? i-1: i) - (st.top()%2==1? st.top()+1: st.top()))/2);
}
st.push(i);
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
1016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
457 ms |
7180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
15020 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
