Submission #395114

#	Time	Username	Problem	Language	Result	Execution time	Memory
395114		ollel	Palindromes (APIO14_palindrome)	C++14	0 / 100	89 ms	114780 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 = 1, size = 0, suffix_link, next_link[26] = {};
};

class eertree {
public:
  const int MAXN = 1000000;
  int n;
  vector<node> nodes;
  int last = 3;

  eertree(string s) {
    n = s.size();
    nodes.resize(MAXN);
    nodes[1].size = -1; nodes[1].suffix_link = 1;
    nodes[2].size = 0; nodes[2].suffix_link = 1;
    int cur, cursize, suff = 1, let;
    rep(pos, 0, n) {
      cur = suff; let = s[pos]-'a';

      while (true) {
        cursize = nodes[cur].size;
        // cout << "FIND "<< cur << " " << pos - cursize - 1 << " " << pos << endl;
        if (pos - cursize - 1 >= 0 && s[pos - cursize - 1] == s[pos]) break;
        cur = nodes[cur].suffix_link;
      }
      // cout << "pos: "<<pos<<endl;

      if (nodes[cur].next_link[let]) {
        // cout << "exists\n" << cur << " to " << let << endl;
        cur = nodes[cur].next_link[let];
        nodes[cur].n++;
        suff = cur;
        // while (cur > 2) {
        //   cout <<cur << " HEHEHE\n" ;
        //   nodes[cur].n++;
        //   cur = nodes[cur].suffix_link;
        // }
      }
      else
      {
        nodes[cur].next_link[let] = last;
        nodes[last].size = nodes[cur].size + 2;
        while (true) {
          // cout << cur << " " << pos - cursize - 1 << " " << pos << endl;
          cursize = nodes[cur].size;
          cur = nodes[cur].suffix_link;
          if (pos - cursize - 1 >= 0 && s[pos - cursize - 1] == s[pos]) {
            nodes[last].suffix_link = max(2, cur);
            // while (cur > 2) {
            //   cout <<cur << " HEHEHE\n" ;
            //   nodes[cur].n++;
            //   cur = nodes[cur].suffix_link;
            // }

            break;
          }
        }
        suff = last;
        last++;
      }
      // cout << last << "!" << endl;
    }
  }
};


int main(){
  string p;
  cin >> p;
  eertree e(p);
  int best = 0;
  for (auto &node : e.nodes) {
    best = max(best, node.n * node.size);
  }
  cout << best << endl;
}

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