Submission #395425

#	Time	Username	Problem	Language	Result	Execution time	Memory
395425		ollel	Palindromes (APIO14_palindrome)	C++17	47 / 100	1089 ms	51808 KiB

palindrome

#include <bits/stdc++.h>
#include <iostream>
#include <string>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
#define rep(i, a, b) for(int i = a; i < b; i++)

struct node {
  int n = 0, size = 0, suffix_link, next[40] = {0};
};

int MAXN = 300300;

class EerTree {
public:
  vector<node> nodes;

  EerTree(string s) {
    nodes.resize(MAXN);
    nodes[1].size = -1; nodes[1].suffix_link = 1;
    nodes[2].size = 0; nodes[2].suffix_link = 1;

    int cur, suff = 2, n = s.size(), cursize, let, last = 3;

    rep(pos, 0, n) {
      cur = suff; let = s[pos] - 'a';

      while (true) {
        cursize = nodes[cur].size;
        if (pos - cursize - 1 >= 0 && s[pos - cursize - 1] == s[pos]) break;
        cur = nodes[cur].suffix_link;
      }

      if (nodes[cur].next[let])
      {
        cur = nodes[cur].next[let];
        nodes[cur].n++;
        int add = cur;
        suff = cur;
        while (add > 2) {add = nodes[add].suffix_link; nodes[add].n++;}
      }
      else
      {
        nodes[last].n = 1;
        nodes[last].size = nodes[cur].size + 2;
        nodes[cur].next[let] = last;

        while (true) {
          cur = nodes[cur].suffix_link;
          cursize = nodes[cur].size;
          if (cur == 1 && nodes[cur].next[let] == last) {
            nodes[last].suffix_link = 2; break;
          }
          if (pos - cursize - 1 >= 0 && s[pos - cursize - 1] == s[pos]) {
            nodes[last].suffix_link = nodes[cur].next[let];
            break;
          }
        }

        int add = nodes[last].suffix_link;
        while (add > 2) {nodes[add].n++; add = nodes[add].suffix_link;}
        suff = last;
        last++;
      }
    }
  }
};

int main() {
  string s;cin>>s;
  EerTree et(s); int k = 0;
  int best = 0;
  for (auto &nd : et.nodes) best = max(best, nd.n * nd.size);
  cout << best << endl;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:72:22: warning: unused variable 'k' [-Wunused-variable]
   72 |   EerTree et(s); int k = 0;
      |                      ^

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