#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
vector<vector<int>> tr;
int l(char c)
{
return int(c) - int('a');
}
int main()
{
tr.resize(2);
tr[0].resize(29);
tr[1].resize(29);
rep(i,26)
{
tr[0][i] = -1;
tr[1][i] = -1;
}
tr[0][26] = 0;
tr[0][27] = -1;
tr[1][26] = 0;
tr[1][27] = 0;
tr[0][28] = 0;
tr[1][28] = 0;
int cu = 1;
string s;
cin>>s;
rep(i,s.size())
{
int c = l(s[i]);
while(i-tr[cu][27]-1 < 0 || l(s[i-tr[cu][27]-1]) != c)
{
cu = tr[cu][26];
}
/* if(i == 3)
{
return 0;
}*/
if(tr[cu][c] == -1)
{
int cu2;
if(cu != 0)
{
cu2 = tr[cu][26];
while(i-tr[cu2][27]-1 < 0 || l(s[i-tr[cu2][27]-1]) != c)
{
cu2 = tr[cu2][26];
}
cu2 = tr[cu2][c];
}
else
{
cu2 = 1;
}
// cout<<cu<<" "<<cu2<<endl;
tr[cu][c] = tr.size();
vector<int> cc;
rep(i,26)
{
cc.pb(-1);
}
cc.pb(cu2);
cc.pb(tr[cu][27] + 2);
cc.pb(1);
tr.pb(cc);
cu = tr[cu][c];
}
else
{
cu = tr[cu][c];
tr[cu][28]++;
}
// cout<<i<<" "<<tr[cu][26]<<" "<<tr[cu][27]<<" "<<tr[cu][28]<<endl;
}
ll ans = 0;
for(int i = tr.size()-1;i>=0;i--)
{
tr[tr[i][26]][28] += tr[i][28];
ans = max(ans,(ll) tr[i][28] * tr[i][27]);
}
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |