Submission #1040076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040076		doducanh	Palindromes (APIO14_palindrome)	C++14	100 / 100	48 ms	69096 KiB

palindrome

///breaker
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
const int maxn=3e5+7;
string s;
struct Node{
    int nxt[26],sufflink;
    ll len,cnt;
    vector<int>edges;
}tree[maxn];
int suff,num;
ll ans=0;
void add(int pos){
    int curr=suff,curr_len=0;
    int letter=s[pos]-'a';
    while(true){
        curr_len=tree[curr].len;
        if(pos-1-curr_len>=0&&s[pos-1-curr_len]==s[pos])break;
        curr=tree[curr].sufflink;
    }
    if(tree[curr].nxt[letter]){
        suff=tree[curr].nxt[letter];
        tree[suff].cnt++;
        return;
    }
    suff=++num;
    tree[num].len=tree[curr].len+2;
    tree[num].cnt=1;
    tree[curr].nxt[letter]=num;
    if(tree[num].len==1){
        tree[num].sufflink=2;
        tree[2].edges.push_back(num);
        return;
    }
    while(true){
        curr=tree[curr].sufflink;
        curr_len=tree[curr].len;
        if(pos-1-curr_len>=0&&s[pos-1-curr_len]==s[pos]){
            tree[num].sufflink=tree[curr].nxt[letter];
            tree[tree[curr].nxt[letter]].edges.push_back(num);
            break;
        }
    }
}
void init(){
    num=2,suff=2;
    tree[1].len=-1;
    tree[2].len=0;
    tree[1].sufflink=1;
    tree[2].sufflink=1;
    tree[1].edges.push_back(2);
}
int dfs(int u=1)
{
    for(int i:tree[u].edges){
        tree[u].cnt+=dfs(i);
    }
    ans=max(ans,tree[u].cnt*tree[u].len);
    return tree[u].cnt;
}
void sol(){
    cin>>s;
    init();
    for(int i=0;i<s.size();i++)add(i);
    dfs();
    cout<<ans;
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

palindrome.cpp: In function 'void sol()':
palindrome.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<s.size();i++)add(i);
      |                 ~^~~~~~~~~
palindrome.cpp: At global scope:
palindrome.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main()
      | ^~~~

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