oj.uz

Submission #140068

# Submission time Handle Problem Language Result Execution time Memory
140068 2019-08-02T01:38:10 Z shamimjucse Palindromes (APIO14_palindrome) C++14
0 / 100
 57 ms 34820 KB 
#include<bits/stdc++.h>
using namespace std;

const int mx = 300005;
struct Node
{
    int len,link,next[26];
};
string s;
Node tr[mx];
int node; /// node 1 - root with len -1, node 2 - root with len 0
int suff; /// max suffix palindrome
inline int New()
{
    node++;
    tr[node].len = 0, tr[node].link = 0;
    memset(tr[node].next, 0, sizeof tr[node].next);
    return node;
}
int cnt[mx];
inline bool Insert(int pos)
{
    int cur = suff, curlen = 0;
    int c = s[pos]-'a'; ///check it
    while(true) ///Finding maximum length palindromic suffix
    {
        curlen = tr[cur].len;
        if (pos-1-curlen>=0 && s[pos-1-curlen]==s[pos])
            break;
        cur = tr[cur].link;
    }
    if(tr[cur].next[c]) ///Existing node
    {
        suff = tr[cur].next[c];
        cnt[suff]++;
        return false;
    }

    suff = New();
    tr[node].len = tr[cur].len + 2;
    tr[cur].next[c] = node;
    if(tr[node].len == 1) ///Single character, connected with root
    {
        tr[node].link = 2;
        cnt[suff]++;
        return true;
    }
    while(true)///Finding suffix link
    {
        cur = tr[cur].link;
        curlen = tr[cur].len;
        if(pos-1-curlen>=0 && s[pos-1-curlen]==s[pos])
        {
            tr[node].link = tr[cur].next[c];
            break;
        }
    }
    cnt[suff]++;
    return true;
}
void initTree()
{
    node = 2, suff = 2;
    tr[1].len = -1, tr[1].link = 1;
    tr[2].len = 0, tr[2].link = 1;
    memset(tr[1].next,0,sizeof tr[1].next);
    memset(tr[2].next,0,sizeof tr[2].next);
}
void buildTree()
{
    initTree();
    for(int i=0;i<s.size();i++)
    {
        Insert(i);
        cnt[tr[suff].link]+=cnt[suff];
    }
}
long long sm = 0;
void count()
{
    for(int i=node;i>2;i--)
    {
        //cnt[tr[i].link]+=cnt[i];
        sm = max(sm,1LL*cnt[i]*tr[i].len);
    }
}
int main()
{
    cin >> s;
    buildTree();
    count();
    cout << sm << endl;
    return 0;
}

Compilation message

palindrome.cpp: In function 'void buildTree()':
palindrome.cpp:72:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++)
                 ~^~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 11896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 34820 KB Output isn't correct
2 Halted 0 ms 0 KB -