Submission #91511

#	Time	Username	Problem	Language	Result	Execution time	Memory
91511		RezwanArefin01	Palindromes (APIO14_palindrome)	C++17	100 / 100	56 ms	39952 KiB

palindrome

///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 3e5 + 10; 

int t[N][26], len[N], link[N], occ[N], idx, suff; 
char s[N]; int n; 

bool extend(int pos) {
    int cur = suff, c = s[pos] - 'a';
    int cnt = 0; 
    while(pos - len[cur] - 1 < 0 || s[pos - len[cur] - 1] != s[pos]) 
        cur = link[cur]; 
    if(t[cur][c]) {
        suff = t[cur][c]; 
        occ[t[cur][c]]++;
        return 0; 
    }
    suff = ++idx; 
    t[cur][c] = idx; 
    len[idx] = len[cur] + 2;    
    occ[idx] = 1; 
    if(len[idx] == 1) {
        link[idx] = 2; 
        return 1;
    }
    cur = link[cur];
    while(pos - len[cur] - 1 < 0 || s[pos - len[cur] - 1] != s[pos]) 
        cur = link[cur]; 
    link[idx] = t[cur][c]; 
    return 1; 
}

void init() {
    len[1] = -1, link[1] = 1; 
    len[2] = 0, link[2] = 1; 
    idx = suff = 2; 
}

int main(int argc, char const *argv[]) {
	scanf("%s", s); n = strlen(s); 

    init(); 
    for(int i = 0; i < n; i++) 
        extend(i); 

    ll ans = 0; 
    for(int i = idx; i >= 3; i--)  {
        occ[link[i]] += occ[i]; 
        ans = max(ans, (ll) len[i] * occ[i]); 
    }
    printf("%lld\n", ans); 
}

Compilation message (stderr)

palindrome.cpp: In function 'bool extend(int)':
palindrome.cpp:15:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = 0; 
         ^~~
palindrome.cpp: In function 'int main(int, const char**)':
palindrome.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s); n = strlen(s); 
  ~~~~~^~~~~~~~~

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