Submission #395572

#	Time	Username	Problem	Language	Result	Execution time	Memory
395572		Victor	Palindromes (APIO14_palindrome)	C++17	100 / 100	49 ms	47048 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

vi dummy(26, -1);

struct node {
    int suflink;
    vi next = dummy;
    ll len;
};

string str;
ll ans = 0;
int currnode = 0, nodes = 1, cnt[300003];
node tree[300003];

void insertNode(int pos) {
    int cur = currnode, curlen = 0;
    int let = str[pos] - 'a';

    while (true) {
        curlen = tree[cur].len;
        if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos])
            break;
        cur = tree[cur].suflink;
    }
    if (tree[cur].next[let] != -1) {
        currnode = tree[cur].next[let];
        return;
    }

    currnode=++nodes;
    tree[nodes].len = tree[cur].len + 2;
    tree[cur].next[let] = nodes;

    if (tree[currnode].len == 1) {
        tree[currnode].suflink = 1;
        return;
    }
    
    while (true) {
        cur = tree[cur].suflink;
        curlen = tree[cur].len;
        if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos]) {
            tree[nodes].suflink = tree[cur].next[let];
            break;
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    memset(cnt, 0, sizeof(cnt));
    cin >> str;

    node root;
    root.len = -1;
    root.suflink = 0;
    tree[0] = root;

    root.len = 0;
    tree[1] = root;

    rep(i, 0, sz(str)) {
        insertNode(i);
        ++cnt[currnode];
    }

    per(i, 2, nodes+1) {
        ans = max(ans, tree[i].len * ll(cnt[i]));
        cnt[tree[i].suflink] += cnt[i];
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i, a, b) for (int i = a; i < (b); ++i)
      |                                        ^
palindrome.cpp:87:5: note: in expansion of macro 'rep'
   87 |     rep(i, 0, sz(str)) {
      |     ^~~

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