Submission #248560

#	Time	Username	Problem	Language	Result	Execution time	Memory
248560		wzy	Palindromes (APIO14_palindrome)	C++11	100 / 100	56 ms	45588 KiB

palindrome

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <climits>

using namespace std;

#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x) , end(x)
#define sz(x) (int)(x).size()
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;

ll modpow(ll b, ll e ,ll mod){
	ll ans = 1;
	for (; e; b = b * b % mod, e /= 2)
		if (e & 1) ans = ans * b % mod;
	return ans;
}
const int N = 300005;
string s;
int bigsuf = -1 , id = 2;
struct node{
	int link , len , occ;
	vi go;
} tree[N];

void init(){
	bigsuf = 2;
	id = 2;
	tree[1].len = -1 , tree[1].link = 1, tree[1].go = vi(26,0) , tree[1].occ = 0;
	tree[2].len = 0 , tree[2].link = 1 , tree[2].go = vi(26,0) , tree[2].occ = 0;
}

void append(int p){
	int cur = bigsuf , c = s[p] - 'a';
	while((p-1-tree[cur].len < 0) || s[p - 1 - tree[cur].len] != s[p])
		cur = tree[cur].link;
	if(!tree[cur].go[c]){
		int link = tree[cur].link;
		while((p-1-tree[link].len < 0) || s[p - 1 - tree[link].len] != s[p])
			link = tree[link].link;		
		tree[cur].go[c] = ++id;
		tree[id].go = vi(26,0);
		tree[id].len = tree[cur].len + 2;
		tree[id].link = (tree[id].len == 1 ? 2 : tree[link].go[c]);
	}
	bigsuf = tree[cur].go[c];
	tree[bigsuf].occ ++ ;
}

int32_t main(){
	int t = 1; 
	for(int ii = 0 ; ii < t ; ii ++){
		cin >> s;
		init();
		for(int i = 0 ; i < sz(s) ; i++){
			append(i);
		}
		ll ans = 0;
		for(int i = id ; i > 2 ; i --){
			tree[tree[i].link].occ += tree[i].occ;
			ans = max(ans , (tree[i].occ * 1ll) * (tree[i].len*1ll)) ; 
		}
		cout << ans << endl;
	}
}

/* clever stuff:
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and STAY ORGANIZED
	* Keep it simple stupid
	* WRITE STUFF DOWN
	* math -> gcd / lcm / divisors? 
*/

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