| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 395766 | abdzag | Palindromes (APIO14_palindrome) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b); i--);
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)
using namespace std;
typedef long long ll;
#define MAXN 1000000;
string s;
const ll inf = 1e15;
struct Node
{
// store start and end indexes of current
// Node inclusively
int start, end;
// stores length of substring
int length;
// stores insertion Node for all characters a-z
int insertEdg[26];
// stores the Maximum Palindromic Suffix Node for
// the current Node
int suffixEdg;
int count;
};
// two special dummy Nodes as explained above
Node root1, root2;
// stores Node information for constant time access
Node tree[MAXN];
// Keeps track the current Node while insertion
int currNode;
int ptr;
map<string, ll> mp;
void insert(int idx)
{
//STEP 1//
/* search for Node X such that s[idx] X S[idx]
is maximum palindrome ending at position idx
iterate down the suffix link of currNode to
find X */
int tmp = currNode;
while (true)
{
int curLength = tree[tmp].length;
if (idx - curLength >= 1 and s[idx] == s[idx - curLength - 1])
break;
tmp = tree[tmp].suffixEdg;
}
/* Now we have found X ....
* X = string at Node tmp
* Check : if s[idx] X s[idx] already exists or not*/
if (tree[tmp].insertEdg[s[idx] - 'a'] != 0)
{
// s[idx] X s[idx] already exists in the tree
currNode = tree[tmp].insertEdg[s[idx] - 'a'];
string curs = "";
mp[curs]++;
return;
}
// creating new Node
ptr++;
// making new Node as child of X with
// weight as s[idx]
tree[tmp].insertEdg[s[idx] - 'a'] = ptr;
// calculating length of new Node
tree[ptr].length = tree[tmp].length + 2;
// updating end point for new Node
tree[ptr].end = idx;
// updating the start for new Node
tree[ptr].start = idx - tree[ptr].length + 1;
string curs = "";
mp[curs]++;
//STEP 2//
/* Setting the suffix edge for the newly created
Node tree[ptr]. Finding some String Y such that
s[idx] + Y + s[idx] is longest possible
palindromic suffix for newly created Node.*/
tmp = tree[tmp].suffixEdg;
// making new Node as current Node
currNode = ptr;
if (tree[currNode].length == 1)
{
// if new palindrome's length is 1
// making its suffix link to be null string
tree[currNode].suffixEdg = 2;
return;
}
while (true)
{
int curLength = tree[tmp].length;
if (idx - curLength >= 1 and s[idx] == s[idx - curLength - 1])
break;
tmp = tree[tmp].suffixEdg;
}
// Now we have found string Y
// linking current Nodes suffix link with s[idx]+Y+s[idx]
tree[currNode].suffixEdg = tree[tmp].insertEdg[s[idx] - 'a'];
}
vector<ll> pi(const string& s) {
vector<ll> p(s.size());
rep(i, 1, s.size()) {
int g = p[i - 1];
while (g && s[i] != s[g]) g = p[g - 1];
p[i] = g + (s[i] == s[g]);
}
return p;
}
ll match(const string& s, const string& pat) {
vector<ll> p = pi(pat + '\0' + s);
ll res=0;
rep(i, p.size() - s.size(), p.size())
if (p[i] == pat.size()) res++;
return res;
}
int main() {
cin.sync_with_stdio(false);
root1.length = -1;
root1.suffixEdg = 1;
root2.length = 0;
root2.suffixEdg = 1;
tree[1] = root1;
tree[2] = root2;
ptr = 2;
currNode = 1;
cin >> s;
int l = s.size();
rep(i, 0, l) insert(i);
ll ans = 0;
rep(i, 2, ptr + 1) {
string curs = "";
rep(j, tree[i].start, tree[i].end + 1) curs += s[j];
ll val = match(s, curs)*curs.size();
ans=max(ans,val);
}
cout << ans << endl;
return 0;
}