Submission #395765

#	Time	Username	Problem	Language	Result	Execution time	Memory
395765		abdzag	Palindromes (APIO14_palindrome)	C++17	23 / 100	15 ms	1752 KiB

palindrome

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b); i--);
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)

using namespace std;

typedef long long ll;
#define MAXN  1000
string s;

const ll inf = 1e15;
struct Node
{
    // store start and end indexes of current
    // Node inclusively
    int start, end;

    // stores length of substring
    int length;

    // stores insertion Node for all characters a-z
    int insertEdg[26];

    // stores the Maximum Palindromic Suffix Node for
    // the current Node
    int suffixEdg;
    
    int count;
};

// two special dummy Nodes as explained above
Node root1, root2;

// stores Node information for constant time access
Node tree[MAXN];

// Keeps track the current Node while insertion
int currNode;
int ptr;
map<string, ll> mp;
void insert(int idx)
{
    //STEP 1//

        /* search for Node X such that s[idx] X S[idx]
           is maximum palindrome ending at position idx
           iterate down the suffix link of currNode to
           find X */
    int tmp = currNode;
    while (true)
    {
        int curLength = tree[tmp].length;
        if (idx - curLength >= 1 and s[idx] == s[idx - curLength - 1])
            break;
        tmp = tree[tmp].suffixEdg;
    }

    /* Now we have found X ....
     * X = string at Node tmp
     * Check : if s[idx] X s[idx] already exists or not*/
    if (tree[tmp].insertEdg[s[idx] - 'a'] != 0)
    {
        // s[idx] X s[idx] already exists in the tree
        currNode = tree[tmp].insertEdg[s[idx] - 'a'];
        string curs = "";
        mp[curs]++;
        return;
    }

    // creating new Node
    ptr++;

    // making new Node as child of X with
    // weight as s[idx]
    tree[tmp].insertEdg[s[idx] - 'a'] = ptr;

    // calculating length of new Node
    tree[ptr].length = tree[tmp].length + 2;

    // updating end point for new Node
    tree[ptr].end = idx;

    // updating the start for new Node
    tree[ptr].start = idx - tree[ptr].length + 1;
    string curs = "";
    mp[curs]++;
    //STEP 2//

        /* Setting the suffix edge for the newly created
           Node tree[ptr]. Finding some String Y such that
           s[idx] + Y + s[idx] is longest possible
           palindromic suffix for newly created Node.*/

    tmp = tree[tmp].suffixEdg;

    // making new Node as current Node
    currNode = ptr;
    if (tree[currNode].length == 1)
    {
        // if new palindrome's length is 1
        // making its suffix link to be null string
        tree[currNode].suffixEdg = 2;
        return;
    }
    while (true)
    {
        int curLength = tree[tmp].length;
        if (idx - curLength >= 1 and s[idx] == s[idx - curLength - 1])
            break;
        tmp = tree[tmp].suffixEdg;
    }

    // Now we have found string Y
    // linking current Nodes suffix link with s[idx]+Y+s[idx]
    tree[currNode].suffixEdg = tree[tmp].insertEdg[s[idx] - 'a'];
}
vector<ll> pi(const string& s) {
    vector<ll> p(s.size());
    rep(i, 1, s.size()) {
        int g = p[i - 1];
        while (g && s[i] != s[g]) g = p[g - 1];
        p[i] = g + (s[i] == s[g]);
    }
    return p;
}

ll match(const string& s, const string& pat) {
    vector<ll> p = pi(pat + '\0' + s);
    ll res=0;
    rep(i, p.size() - s.size(), p.size())
        if (p[i] == pat.size()) res++;
    return res;
}
int main() {
    cin.sync_with_stdio(false);
    root1.length = -1;
    root1.suffixEdg = 1;
    root2.length = 0;
    root2.suffixEdg = 1;

    tree[1] = root1;
    tree[2] = root2;
    ptr = 2;
    currNode = 1;
    cin >> s;
    int l = s.size();
    rep(i, 0, l) insert(i);
    ll ans = 0;
    rep(i, 2, ptr + 1) {
        string curs = "";
        rep(j, tree[i].start, tree[i].end + 1) curs += s[j];
        ll val = match(s, curs)*curs.size();
        ans=max(ans,val);
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'll match(const string&, const string&)':
palindrome.cpp:134:18: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         if (p[i] == pat.size()) res++;

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