Submission #392253

#	Time	Username	Problem	Language	Result	Execution time	Memory
392253		BorisBarca	Palindromes (APIO14_palindrome)	C++14	47 / 100	8 ms	3668 KiB

palindrome

/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define SQ(a) (a) * (a)
#define TRACE(x) cout << #x " = " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define umap unordered_map

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <string> vs;

const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;

inline int sum(int a, int b){
	if (a + b < 0)
		return (a + b + MOD) % MOD;
	return (a + b) % MOD;
}

inline void add(int &a, int b){
	a = sum(a, b);
}

inline int mul(ll a, ll b){
	return ((a % MOD) * ((ll)b % MOD)) % MOD;
}

inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}

inline int fast_pot(ll pot, ll n){
	ll ret = 1;
	while (n){
		if (n & 1LL)
			ret = (ret * pot) % MOD;
		pot = (pot * pot) % MOD;
		n >>= 1LL;
	}
	return ret;
}

//radim palindromsko stablo

const int N = 1e4 + 10;

struct node{
	int next[26];
	int len;
	int sufflink;
	int num;
	int lazy;
};

int len;
string s;
node stablo[N];
int num;
int suff;
ll ans;

bool addLetter(int pos){
	int cur = suff, curlen = 0;
	int let = s[pos] - 'a';
	
	while (true){
		curlen = stablo[cur].len;
		if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
			break;
		cur = stablo[cur].sufflink;
	}
	if (stablo[cur].next[let]){
		suff = stablo[cur].next[let];
		stablo[stablo[cur].next[let]].lazy++;
		return false;
	}

	num++;
	suff = num;
	stablo[num].len = stablo[cur].len + 2;
	stablo[cur].next[let] = num;

	if (stablo[num].len == 1){
		stablo[num].sufflink = 2;
		stablo[num].num = 1;
		stablo[num].lazy++;
		return true;
	}

	while (true){
		cur = stablo[cur].sufflink;
		curlen = stablo[cur].len;
		if (pos - 1  - curlen >= 0 && s[pos - 1 - curlen] == s[pos]){
			stablo[num].sufflink = stablo[cur].next[let];
			break;
		}
	}

	stablo[num].num = 1 + stablo[stablo[num].sufflink].num;
	stablo[num].lazy++;
	return true;
}

void initstablo(){
	num = 2, suff = 2;
	stablo[1].len = -1, stablo[1].sufflink = 1;
	stablo[2].len = 0, stablo[2].sufflink = 1;
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> s;
	len = sz(s);

	initstablo();
	REP(i, len){
		addLetter(i);
		//ans += stablo[suff].num;
	}

	ll sol = 0;
	for (int i = num; i > 2; --i){
		//cout << i _ stablo[i].len _ stablo[i].lazy << '\n';
		sol = max(sol, (ll)stablo[i].lazy * stablo[i].len);
		stablo[stablo[i].sufflink].lazy += stablo[i].lazy;
	}
	cout << sol << '\n';	

	return 0;
}

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