Submission #395387

#	Time	Username	Problem	Language	Result	Execution time	Memory
395387		ollel	Palindromes (APIO14_palindrome)	C++14	0 / 100	96 ms	131076 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, size, suffix_link, next[40] = {0};
};

int MAXN = 1000000;

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';
      // cout << pos << " " << s[pos] << " "<< cur << " " << nodes[cur].suffix_link << endl;

      while (true) {
        cursize = nodes[cur].size;
        // cout << cur << " " << nodes[cur].suffix_link <<" "<< cursize << endl;
        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 = nodes[cur].suffix_link;
        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) {
          // cout << cur << endl;
          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;
          }
        }
        // cout << "new " << last << ", suffix link: " << nodes[last].suffix_link << endl;

        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 best = 0;
  for (auto &nd : et.nodes) best = max(best, nd.n * nd.size);
  // for (auto &nd : et.nodes) cout << nd.n << " " << nd.size << " " << endl;
  cout << best << endl;
}

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