#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 100005
#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++)
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
11992 KB |
Output is correct |
2 |
Correct |
15 ms |
12276 KB |
Output is correct |
3 |
Correct |
15 ms |
12276 KB |
Output is correct |
4 |
Correct |
12 ms |
12276 KB |
Output is correct |
5 |
Correct |
14 ms |
12276 KB |
Output is correct |
6 |
Correct |
14 ms |
12276 KB |
Output is correct |
7 |
Correct |
14 ms |
12360 KB |
Output is correct |
8 |
Correct |
11 ms |
12360 KB |
Output is correct |
9 |
Correct |
12 ms |
12376 KB |
Output is correct |
10 |
Correct |
13 ms |
12376 KB |
Output is correct |
11 |
Correct |
15 ms |
12376 KB |
Output is correct |
12 |
Correct |
12 ms |
12376 KB |
Output is correct |
13 |
Correct |
12 ms |
12376 KB |
Output is correct |
14 |
Correct |
11 ms |
12376 KB |
Output is correct |
15 |
Correct |
11 ms |
12376 KB |
Output is correct |
16 |
Correct |
11 ms |
12376 KB |
Output is correct |
17 |
Correct |
11 ms |
12376 KB |
Output is correct |
18 |
Correct |
12 ms |
12376 KB |
Output is correct |
19 |
Correct |
15 ms |
12376 KB |
Output is correct |
20 |
Correct |
13 ms |
12376 KB |
Output is correct |
21 |
Correct |
12 ms |
12376 KB |
Output is correct |
22 |
Correct |
15 ms |
12376 KB |
Output is correct |
23 |
Correct |
14 ms |
12376 KB |
Output is correct |
24 |
Correct |
15 ms |
12376 KB |
Output is correct |
25 |
Correct |
15 ms |
12392 KB |
Output is correct |
26 |
Correct |
11 ms |
12424 KB |
Output is correct |
27 |
Correct |
14 ms |
12424 KB |
Output is correct |
28 |
Correct |
14 ms |
12508 KB |
Output is correct |
29 |
Correct |
11 ms |
12508 KB |
Output is correct |
30 |
Correct |
14 ms |
12508 KB |
Output is correct |
31 |
Correct |
12 ms |
12508 KB |
Output is correct |
32 |
Correct |
12 ms |
12572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
12572 KB |
Output is correct |
2 |
Correct |
12 ms |
12572 KB |
Output is correct |
3 |
Correct |
11 ms |
12572 KB |
Output is correct |
4 |
Correct |
13 ms |
12572 KB |
Output is correct |
5 |
Correct |
11 ms |
12572 KB |
Output is correct |
6 |
Correct |
12 ms |
12572 KB |
Output is correct |
7 |
Correct |
11 ms |
12572 KB |
Output is correct |
8 |
Correct |
12 ms |
12592 KB |
Output is correct |
9 |
Correct |
12 ms |
12592 KB |
Output is correct |
10 |
Correct |
11 ms |
12592 KB |
Output is correct |
11 |
Correct |
12 ms |
12592 KB |
Output is correct |
12 |
Correct |
11 ms |
12592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12648 KB |
Output is correct |
2 |
Correct |
12 ms |
12680 KB |
Output is correct |
3 |
Correct |
12 ms |
12712 KB |
Output is correct |
4 |
Correct |
14 ms |
12736 KB |
Output is correct |
5 |
Correct |
12 ms |
12748 KB |
Output is correct |
6 |
Correct |
12 ms |
12776 KB |
Output is correct |
7 |
Correct |
12 ms |
12788 KB |
Output is correct |
8 |
Correct |
11 ms |
12800 KB |
Output is correct |
9 |
Correct |
11 ms |
12800 KB |
Output is correct |
10 |
Correct |
12 ms |
12824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
13092 KB |
Output is correct |
2 |
Correct |
18 ms |
13196 KB |
Output is correct |
3 |
Correct |
19 ms |
13332 KB |
Output is correct |
4 |
Correct |
18 ms |
13432 KB |
Output is correct |
5 |
Correct |
17 ms |
13620 KB |
Output is correct |
6 |
Correct |
16 ms |
13632 KB |
Output is correct |
7 |
Correct |
20 ms |
13732 KB |
Output is correct |
8 |
Correct |
18 ms |
13816 KB |
Output is correct |
9 |
Correct |
15 ms |
13932 KB |
Output is correct |
10 |
Correct |
21 ms |
14032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
34 ms |
26812 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |