Submission #248609

#	Time	Username	Problem	Language	Result	Execution time	Memory
248609		wzy	Palindromes (APIO14_palindrome)	C++11	100 / 100	56 ms	45332 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;
int bigsuf , id;
struct node{
	int link , len , oc = 0;
	vi go;
} tree[N];

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

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


int32_t main(){
	cin >> s;
	init();
	rep(i,0,sz(s)) append(i);
	ll ans = 0;
	for(int j = id ;j > 2 ; j --){
		tree[tree[j].link].oc += tree[j].oc;
		ans = max(ans , ((1ll * tree[j].len)) * ((1ll * tree[j].oc)));
	}	
	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