#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define gc getchar
#define pc putchar
#else
#define gc getchar_unlocked
#define pc putchar_unlocked
#endif
using namespace std;
#define vi vector<int>
#define si set<int>
#define vs vector<string>
#define pii pair<int,int>
#define vpi vector<pii>
#define pri priority_queue<int>
#define rev_pri priority_queue<int,vector<int>,greater<int> >
#define mpi map<int,int>
#define i64 long long int
#define endl '\n'
#define pi acos(-1)
#define all(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf INT_MAX/2
#define infll LLONG_MAX/3
#define For(i,n) for(int i=0;i<n;i++)
#define Fre(i,a,b) for(int i = a; i < b; i++)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pfn(n) printf("%d\n", n)
#define pfs(n) printf("%d ", n)
#define eps 1e-8
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define READ freopen("in.txt", "r", stdin)
#define WRITE freopen("out.txt", "w", stdout)
#define sz size()
#define dbg(i) printf("yo %d\n", i)
#define foreach(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define sqr(a) (a) * (a)
#define clr clear()
#define CASE(a) printf("Case #%d: ",a)
//int dx[] = {0,1,0,-1,1,1,-1,-1};
//int dy[] = {1,0,-1,0,1,-1,-1,1};
//i64 gcd(i64 a,i64 b){if(!b)return a;return gcd(b,a%b);}
//inline void fastRead(int *a){register char c=0;while(c<33)c=gc();*a=0;while(c>33){*a=*a*10+c-'0';c=gc();}}
//inline void fastWrite(int a){char snum[20];int i=0;do{snum[i++]=a%10+48;a=a/10;}while(a!=0);i=i-1;while(i>=0)pc(snum[i--]);pc('\n');}
//i64 bigmod(i64 num,i64 n){if(n==0)return 1;i64 x=bigmod(num,n/2);x=x*x%mod;if(n%2==1)x=x*num%mod;return x;}
//i64 modinverse(i64 num){return bigmod(num,mod-2)%mod;}
//i64 po(i64 a,i64 b){i64 ans=1;while(b--)ans *= a;return ans;}
//i64 ncr(i64 n,i64 r){if(n==r)return 1;if(r==1)return n;if(dp[n][r]!=-1)return dp[n][r];return dp[n][r]=ncr(n-1,r)+ncr(n-1,r-1);}
// bit manipulations
//bool checkbit(int mask,int bit){return mask & (1<<bit);}
//int setbit(int mask,int bit){ return mask (1<<bit) ; }
//int clearbit(int mask,int bit){return mask & ~(1<<bit);}
//int togglebit(int mask,int bit){return mask ^ (1<<bit);}
// Code from https://rezwanarefin01.github.io/posts/palindromic-tree-01/
/*
Concept:
aba -> tree[nodeNumber][c] means -> cabac , adding c in both side
for odd length, define one root and consider the length -1
Suffix Link: biggest proper suffix ( length < string length) which is also a palindrome
if no proper suffix , link to root with length 0
length 0 root links back to length -1 root
length -1 root links to own node
tree[node][character] -> trie info
len[node] -> length of the node
link[node] -> suffix link
last = holds the max palindrome suffix of the processed prefix till now
endsAt[node] -> total palindrome ends at i
fact 1: N length string can only have N distinct palindrome
fact 2: Palindrome tree holds all distinct palindrome
fact 3: number of distinct palindrome = freeNode - 2
fact 4: number of total palindrome = sum of( endsAt[i]) 0 to freeNode
fact 5: freq[node] will give us total freq of palindrome at node i
*/
#define mxn 3000006
mpi tree[mxn];
int freeNode;
int len[mxn], link[mxn], last;
string s;
//int endsAt[mxn];
int freq[mxn];
void extend(int p) {
while(s[p - len[last] - 1] != s[p])
last = link[last];
int x = link[last], c = s[p] - 'a';
while(s[p - len[x] - 1] != s[p])
x = link[x];
if(!tree[last][c]) {
tree[last][c] = ++freeNode;
len[freeNode] = len[last] + 2;
link[freeNode] = len[freeNode] == 1 ? 2 : tree[x][c];
// endsAt[freeNode] = endsAt[link[freeNode]] + 1;
}
last = tree[last][c];
freq[last]++;
}
void ini() {
// mem(tree,0);
mem(len,0);
mem(link,0);
// mem(endsAt,0);
mem(freq,0);
len[1] = -1, link[1] = 1;
len[2] = 0, link[2] = 1;
freeNode = last = 2;
}
void inputAndBuild() {
ini();
cin >> s;
s = "$" + s;
Fre(i,1,s.sz)
extend(i);
for(int i = freeNode ; i > 2 ; i--) freq[link[i]] += freq[i];
}
int main() {
inputAndBuild();
i64 ans = 0;
For(i,freeNode + 1)
ans = max(ans, (i64)len[i] * freq[i]);
cout << ans << endl;
return 0;
}
Compilation message
palindrome.cpp: In function 'void inputAndBuild()':
palindrome.cpp:31:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define Fre(i,a,b) for(int i = a; i < b; i++)
^
palindrome.cpp:145:9: note: in expansion of macro 'Fre'
Fre(i,1,s.sz)
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
112 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
109 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
108 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
