Submission #155262

#	Time	Username	Problem	Language	Result	Execution time	Memory
155262		BrehamPie	Palindromes (APIO14_palindrome)	C++14	100 / 100	68 ms	37492 KiB

palindrome

#include<bits/stdc++.h>
#define FastIO      ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define pb          push_back
#define siz         100009
#define inf         1e9+8
#define mp          make_pair
#define rep(i,n)    for(int i=0;i<n;i++)
#define repo(i,m,n) for(int i=m;i<=n;i++)
#define ll          long long
#define pii         pair<int,int >
#define sc(n)       scanf("%d",&n)
#define sc2(m,n)    scanf("%d%d",&m,&n);
#define MOD         4294967296
#define fileout     freopen("output.txt","w",stdout)
#define filein      freopen("input.txt","r",stdin)
#define mem(x,i)    memset(x,i,sizeof x)
#define PI          acos(-1.0)
#define ff          first
#define ss          second
#define all(x)      x.begin(),x.end()
#define Case(t)     for(int ks=1;ks<=t;ks++)
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
const int N=3e5+10;
int tree[N][26],idx;
ll len[N];int link[N];
int ans[N],occ[N];
int t;
string str;
void extend(int p)
{
    while(str[p-len[t]-1]!=str[p])
        t=link[t];
    int x=link[t],c=str[p]-'a';
    while(str[p-len[x]-1]!=str[p])
        x=link[x];
    if(!tree[t][c])
    {
        tree[t][c]=++idx;
        len[idx]=len[t]+2;
        link[idx]=(len[idx]==1?2:tree[x][c]);
        ans[idx]=1+ans[link[idx]];
    }
    t=tree[t][c];
    ++occ[t];
}
int main()
{

    {
        mem(tree,0);
        len[1]=-1;
        len[2]=0;
        link[1]=link[2]=1;
        idx=t=2;
        cin>>str;
        str=' '+str;
        int n=str.size();
        ll val=0;
        for(int i=1; i<str.size(); i++)
        {
            extend(i);
            //val+=ans[t];
        }
        for(int i=idx;i>2;i--) occ[link[i]]+=occ[i];
        for(int i=3;i<=idx;i++)val=max(val,occ[i]*len[i]);
        printf("%lld\n",val);
    }
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=1; i<str.size(); i++)
                      ~^~~~~~~~~~~
palindrome.cpp:65:13: warning: unused variable 'n' [-Wunused-variable]
         int n=str.size();
             ^

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27