Submission #395482

#	Time	Username	Problem	Language	Result	Execution time	Memory
395482		ollel	Palindromes (APIO14_palindrome)	C++17	47 / 100	89 ms	69452 KiB

palindrome

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

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

int MAXN = 300300;

class EerTree {
public:
  vector<node> nodes;
  vvi sufto;

  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++;
        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++;
      }
    }
    queue<int> children;bool c;

    vector<bool> issuf(last, true);
    vvi sufto(last);
    rep(i, 1, last) {
      issuf[nodes[i].suffix_link] = false;
      sufto[nodes[i].suffix_link].push_back(i);
    }

    rep(i, 1, last) {
      if (issuf[i]) children.push(i);
    }

    int x;
    while (!children.empty()) {
      x = children.front(); children.pop();
      if (x <= 2 || nodes[x].f) continue;
      nodes[nodes[x].suffix_link].n += nodes[x].n;
      nodes[x].f = true;

      x = nodes[x].suffix_link;
      bool a = true;
      for (auto &nd : sufto[x]) if (!nodes[nd].f) a = false;
      if (a) children.push(x);
    }
  }
};

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

Compilation message (stderr)

palindrome.cpp: In constructor 'EerTree::EerTree(std::string)':
palindrome.cpp:62:13: warning: unused variable 'add' [-Wunused-variable]
   62 |         int add = nodes[last].suffix_link;
      |             ^~~
palindrome.cpp:68:30: warning: unused variable 'c' [-Wunused-variable]
   68 |     queue<int> children;bool c;
      |                              ^

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