Submission #1102745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102745		vjudge1	Palindromes (APIO14_palindrome)	C++17	73 / 100	38 ms	35032 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// struct PAM {
//     // 0 -> even root, 1 -> odd root
//     static constexpr int ALPHABET_SIZE = 26;
//     struct Node {
//         int len, fail;
//         array<int, ALPHABET_SIZE> next;
//         Node() : len{}, fail{}, next{} {}
//     };
//     vector<int> s;
//     vector<Node> t;
//     PAM() { init(); }
//     void init() {
//         t.assign(2, Node());
//         s.clear(); t[1].len = -1;
//         t[0].len = 0, t[0].fail = 1;
//     }
//     int newNode() {
//         t.emplace_back();
//         return t.size() - 1;
//     }
//     int extend(int p, int c) {
//         int n = s.size();
//         s.push_back(c);
//         while (s[n - t[p].len - 1] != c)
//             p = t[p].fail;
//         if (!t[p].next[c]) {
//             int r = newNode();
//             t[r].len = t[p].len + 2;
//             int cur = t[p].fail;
//             while (s[n - t[cur].len - 1] != c)
//                 cur = t[cur].fail;
//             t[r].fail = t[cur].next[c];
//             t[p].next[c] = r;
//         }
//         p = t[p].next[c];
//         return p;
//     }
// };

const int N = 3E5;
struct PAM {
  int ch[N][26], cnt[N], fail[N], len[N], sz;
  string s;
  // 0 -> even root, 1 -> odd root
  PAM () {}
  void init(string s) {
    sz = 0, extend(), extend();
    len[0] = 0, fail[0] = 1, len[1] = -1;
    int lst = 1;
    for (int i = 0; i < s.length(); ++i) {
      while (s[i - len[lst] - 1] != s[i])
        lst = fail[lst];
      if (!ch[lst][s[i] - 'a'])  {
        int idx = extend();
        len[idx] = len[lst] + 2;
        int now = fail[lst];
        while (s[i - len[now] - 1] != s[i])
          now = fail[now];
        fail[idx] = ch[now][s[i] - 'a'];
        ch[lst][s[i] - 'a'] = idx;
      }
      lst = ch[lst][s[i] - 'a'], cnt[lst]++;
    }
  }
  void build_count() {
    for (int i = sz - 1; i > 1; --i)
      cnt[fail[i]] += cnt[i];
  }
  int extend() {
    fill(ch[sz], ch[sz] + 26, 0), sz++;
    return sz - 1;
  }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.length();
    // vector<int> last(n + 1);
    // last[0] = 1;
    PAM pam;
    // for (int i = 0; i < n; i++) {
    //     last[i + 1] = pam.extend(last[i], s[i] - 'a');
    // }

    // int sz = pam.t.size();
    // vector<int> cnt(sz);

    // for (int i = 1; i <= n; i++) {
    //     cnt[last[i]]++; // 去重 = 1
    // }
    // ll ans = 0;
    // for (int i = sz - 1; i > 1; i--) {
    //     cnt[pam.t[i].fail] += cnt[i];
    //     ans = max(ans, 1LL * pam.t[i].len * cnt[i]);
    // }

    // cout << ans << "\n";
    pam.init(s);
    pam.build_count();
    ll ans = 0;
    for (int i = 2; i < pam.sz; i++) {
        ans = max(ans, 1LL * pam.len[i] * pam.cnt[i]);
    }
    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

palindrome.cpp: In member function 'void PAM::init(std::string)':
palindrome.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < s.length(); ++i) {
      |                     ~~^~~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:86:9: warning: unused variable 'n' [-Wunused-variable]
   86 |     int n = s.length();
      |         ^

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