Submission #140065

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
140065	2019-08-02 01:35:23	shamimjucse	Palindromes (APIO14_palindrome)	C++14	100 / 100	70 ms	36408 KiB

palindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mx = 300005;
int tr[mx][26], node;
int len[mx], link[mx],suff;
string s; /// 1-indexed
int cnt[mx],occ[mx];
inline void Insert(int p)
{
    while(s[p - len[suff] - 1] != s[p])
        suff = link[suff];
    int x = link[suff], c = s[p] - 'a';
    while(s[p - len[x] - 1] != s[p])
        x = link[x];
    if(!tr[suff][c])
    {
        tr[suff][c] = ++node;
        len[node] = len[suff] + 2;
        link[node] = (len[node] == 1) ? 2 : tr[x][c];
        cnt[node]+=1 + cnt[link[node]];
    }
    suff = tr[suff][c];
    occ[suff]++;
}
void initTree()
{
    node = 2, suff = 2;
    len[1] = -1, link[1] = 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

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

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