oj.uz

Submission #46580

# Submission time Handle Problem Language Result Execution time Memory
46580 2018-04-21T14:30:34 Z tieunhi Palindromes (APIO14_palindrome) C++14
0 / 100
 2 ms 352 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 2000005
#define maxc 1000000007

using namespace std;

string s;
int sz, cur;

struct PTNode
{
    int first, length, occurance, suffix, child[26];
    PTNode(int first = 0, int length = 0) : first(first), length(length)
    {
        occurance = suffix = 0;
        for (int i = 0; i < 26; i++) child[i] = 0;
    }
}node[N];

void add(int pos)
{
    int start;
    while (1)
    {
        start = pos - node[cur].length - 1;
        if (start >= 0 && s[start] == s[pos])
            break;
        cur = node[cur].suffix;
    }

    int z = s[pos] - 'a';
    if (node[cur].child[z])
    {
        cur = node[cur].child[z];
        node[cur].occurance++;
        return;
    }

    node[++sz] = PTNode(start, node[cur].length + 2);
    node[cur].child[z] = sz;
    if (node[sz].length == 1)
        node[sz].suffix = 2;
    else
    {
        while (1)
        {
            cur = node[cur].suffix;
            int start = pos - node[cur].length - 1;
            if (start >= 0 && s[start] == s[pos])
                break;
        }
        node[sz].suffix = node[cur].child[z];
    }
    node[sz].occurance++;
    cur = sz;
    return;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> s;
    sz = cur = 2;
    node[1] = PTNode(0, -1); node[2] = PTNode(0, 0);
    node[1].suffix = node[2].suffix = 1;
    for (int i = 0; i < s.size(); i++)
        add(i);
    long long res = 0;
    for (int i = sz; i >= 3; i--)
    {
        node[node[i].suffix].occurance += node[i].occurance;
        res = max(res, 1ll*node[i].occurance*node[i].length);
    }
    cout <<res;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:70:23: 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 Runtime error 1 ms 256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -