Submission #621139

#	Time	Username	Problem	Language	Result	Execution time	Memory
621139		socpite	Palindromes (APIO14_palindrome)	C++14	100 / 100	63 ms	66624 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 3e5+5;

int cnt = 2;
int lnk[maxn], go[maxn][26], len[maxn];
ll dp[maxn];
ll ans = 0;
vector<int> tree[maxn];

string str;

void dfs(int x){
    for(auto v: tree[x]){
        dfs(v);
        dp[x]+=dp[v];
    }
    ans = max(ans, dp[x]*len[x]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> str;
    str = '#'+str;
    len[0]=-1;
    len[1]=0;
    int crr = 1;
    for(int i = 1; i < str.length(); i++){
        int id = str[i]-'a';
        while(crr && str[i] != str[i-len[crr]-1])crr = lnk[crr];
        if(go[crr][id])crr = go[crr][id];
        else{
            int tmp = lnk[crr];
            while(tmp && str[i] != str[i-len[tmp]-1])tmp = lnk[tmp];
            if(!go[tmp][id])lnk[cnt]=1;
            else lnk[cnt]=go[tmp][id];
            go[crr][id]=cnt;
            len[cnt]=len[crr]+2;
            crr = cnt;
            cnt++;
        }
        dp[crr]++;
    }
    for(int i = 1; i < cnt; i++)tree[lnk[i]].push_back(i);
    dfs(0);
    cout << ans;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i = 1; i < str.length(); i++){
      |                    ~~^~~~~~~~~~~~~~

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