Submission #498675

#	Time	Username	Problem	Language	Result	Execution time	Memory
498675		BrehamPie	Palindromes (APIO14_palindrome)	C++14	100 / 100	36 ms	39024 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
using ll = long long;
// cnt - number of palindromic suffixes of the node.
// make string 1 indexed.
struct PalindromicTree {
    struct node {
        int nxt[26], len, st, en, link, cnt, oc;
    };
    string s;
    vector<node>t;
    int sz, last;
    PalindromicTree() {}
    PalindromicTree( string _s ) {
        s = _s;
        int n = s.size();
        t.resize( n + 5, node() );
        sz = 2;
        last = 2;
        t[1].len = -1, t[1].link = 1;
        t[2].len = 0, t[2].link = 1;
    }
    // returns 1 if new palindrome is found
    int extend( int pos ) {
        while (s[pos - t[last].len - 1] != s[pos]) last = t[last].link;
        int ch = s[pos] - 'a', x = t[last].link;
        while (s[pos - t[x].len - 1] != s[pos]) x = t[x].link;
        if (t[last].nxt[ch]) {
            last = t[last].nxt[ch];
            t[last].oc++;
            return 0;
        }
        sz++;
        t[sz].oc = 1;
        t[sz].len = t[last].len + 2;
        t[last].nxt[ch] = sz;
        last = sz;
        t[sz].en = pos;
        t[sz].st = pos - t[sz].len + 1;
        if (t[sz].len == 1) {
            t[sz].link = 2, t[sz].cnt = 1;
        } else {
            t[sz].cnt = 1 + t[x].cnt, t[sz].link = t[x].nxt[ch];
        }
        return 1;
    }
    void calc_occ() {
        for (int i = sz; i >= 3; i--) t[t[i].link].oc += t[i].oc;
    }
    ll ans(){
        ll ret = 0;
        for(int i=3;i<=sz;i++){
            ret = max(ret,1ll*t[i].oc*t[i].len*1ll);
        }
        return ret;
    }

};
int main() {
    string str;
    cin >> str;
    str = '#' + str;
    PalindromicTree pt( str );
    for (int i = 1; i < str.size(); i++) {
        pt.extend( i );
    }
    pt.calc_occ();
    cout<<pt.ans()<<endl;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 1; i < str.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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