Submission #171655

#	Time	Username	Problem	Language	Result	Execution time	Memory
171655		njrafi	Palindromes (APIO14_palindrome)	C++14	73 / 100	34 ms	12692 KiB

palindrome

#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
#define gc getchar
#define pc putchar
#else
#define gc getchar_unlocked
#define pc putchar_unlocked
#endif

using namespace std;

#define vi vector<int>
#define si set<int>
#define vs vector<string>
#define pii pair<int,int>
#define vpi vector<pii>
#define pri priority_queue<int>
#define rev_pri priority_queue<int,vector<int>,greater<int> >
#define mpi map<int,int>
#define i64 long long int
#define endl '\n'
#define pi acos(-1)
#define all(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf INT_MAX/2
#define infll LLONG_MAX/3
#define For(i,n) for(int i=0;i<n;i++)
#define Fre(i,a,b) for(int i = a; i < b; i++)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pfn(n) printf("%d\n", n)
#define pfs(n) printf("%d ", n)
#define eps 1e-8
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define READ freopen("in.txt", "r", stdin)
#define WRITE freopen("out.txt", "w", stdout)
#define sz size()
#define dbg(i) printf("yo %d\n", i)
#define foreach(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define sqr(a) (a) * (a)
#define clr clear()
#define CASE(a) printf("Case #%d: ",a)

//int dx[] = {0,1,0,-1,1,1,-1,-1};
//int dy[] = {1,0,-1,0,1,-1,-1,1};


//i64 gcd(i64 a,i64 b){if(!b)return a;return gcd(b,a%b);}

//inline void fastRead(int *a){register char c=0;while(c<33)c=gc();*a=0;while(c>33){*a=*a*10+c-'0';c=gc();}}

//inline void fastWrite(int a){char snum[20];int i=0;do{snum[i++]=a%10+48;a=a/10;}while(a!=0);i=i-1;while(i>=0)pc(snum[i--]);pc('\n');}

//i64 bigmod(i64 num,i64 n){if(n==0)return 1;i64 x=bigmod(num,n/2);x=x*x%mod;if(n%2==1)x=x*num%mod;return x;}

//i64 modinverse(i64 num){return bigmod(num,mod-2)%mod;}

//i64 po(i64 a,i64 b){i64 ans=1;while(b--)ans *= a;return ans;}

//i64 ncr(i64 n,i64 r){if(n==r)return 1;if(r==1)return n;if(dp[n][r]!=-1)return dp[n][r];return dp[n][r]=ncr(n-1,r)+ncr(n-1,r-1);}


// bit manipulations

//bool checkbit(int mask,int bit){return mask & (1<<bit);}

//int setbit(int mask,int bit){ return mask  (1<<bit) ; }

//int clearbit(int mask,int bit){return mask & ~(1<<bit);}

//int togglebit(int mask,int bit){return mask ^ (1<<bit);}



// Code from https://rezwanarefin01.github.io/posts/palindromic-tree-01/

/*
Concept:
aba -> tree[nodeNumber][c] means -> cabac , adding c in both side
for odd length, define one root and consider the length -1
Suffix Link: biggest proper suffix ( length < string length) which is also a palindrome
if no proper suffix , link to root with length 0
length 0 root links back to length -1 root
length -1 root links to own node

tree[node][character] -> trie info
len[node] -> length of the node
link[node] -> suffix link
last = holds the max palindrome suffix of the processed prefix till now
endAt[node] -> total palindrome ends at i

fact 1: N length string can only have N distinct palindrome
fact 2: Palindrome tree holds all distinct palindrome
fact 3: number of distinct palindrome = freeNode - 2
fact 4: number of total palindrome = sum of( endsAt[i]) 0 to freeNode
*/

#define mxn 100005
int tree[mxn][26], freeNode;
int len[mxn], link[mxn], last;
string s;

//int endAt[mxn];
int freq[mxn];

void extend(int p) {
	while(s[p - len[last] - 1] != s[p])
		last = link[last];
	int x = link[last], c = s[p] - 'a';
	while(s[p - len[x] - 1] != s[p])
		x = link[x];
	if(!tree[last][c]) {
		tree[last][c] = ++freeNode;
		len[freeNode] = len[last] + 2;
		link[freeNode] = len[freeNode] == 1 ? 2 : tree[x][c];
//		endAt[freeNode] = endAt[link[freeNode]] + 1;
	}
	last = tree[last][c];
	freq[last]++;
}

void ini() {
	mem(tree,0);
	mem(len,0);
	mem(link,0);
//	mem(endAt,0);
	mem(freq,0);
	len[1] = -1, link[1] = 1;
	len[2] = 0, link[2] = 1;
	freeNode = last = 2;
}

void inputAndBuild() {
	ini();
        cin >> s;
        s = "$" + s;
        Fre(i,1,s.sz)
		extend(i);
        for(int i = freeNode ; i > 2 ; i--) freq[link[i]] += freq[i];
}


int main() {

        inputAndBuild();
        i64 ans = 0;
	For(i,freeNode + 1)
		ans = max(ans, (i64)len[i] * freq[i]);
	cout << ans << endl;









	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'void inputAndBuild()':
palindrome.cpp:31:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define Fre(i,a,b) for(int i = a; i < b; i++)
                                     ^
palindrome.cpp:143:9: note: in expansion of macro 'Fre'
         Fre(i,1,s.sz)
         ^~~

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