Submission #648697

#	Time	Username	Problem	Language	Result	Execution time	Memory
648697		ymm	Palindromes (APIO14_palindrome)	C++17	100 / 100	148 ms	73900 KiB

palindrome

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 300'010;
const int alpha = 26;
int longest_palin[N];
int second_longest[N];
string s;
int n;

struct node {
	int link = 0;
	int next[alpha] = {};
	int len = 0;
	int cnt = 0;
	bool vis = 0;
} pool[10000000];

int rt = 1;

int make_node()
{
	static int nxt = 2;
	return nxt++;
}

int lst_node = rt;
vector<int> all_nodes = {rt};
void insert_node(char c)
{
	c -= 'a';
	int new_node = make_node();
	all_nodes.push_back(new_node);
	pool[new_node].cnt = 1;
	pool[new_node].len = pool[lst_node].len + 1;
	int cur = lst_node;
	lst_node = new_node;
	while (cur) {
		if (!pool[cur].next[c]) {
			pool[cur].next[c] = new_node;
			cur = pool[cur].link;
		} else {
			break;
		}
	}
	if (!cur) {
		pool[new_node].link = rt;
		return;
	}
	int q = pool[cur].next[c];
	if (pool[cur].len + 1 == pool[q].len) {
		pool[new_node].link = q;
		return;
	}
	int clone = make_node();
	all_nodes.push_back(clone);
	pool[clone] = pool[q];
	pool[clone].cnt = 0;
	pool[clone].len = pool[cur].len + 1;
	pool[q].link = clone;
	while (cur && pool[cur].next[c] == q) {
		pool[cur].next[c] = clone;
		cur = pool[cur].link;
	}
	pool[new_node].link = clone;
}

int index2node[N];

void make_automata()
{
	Loop (i,0,n) {
		insert_node(s[i]);
		index2node[i] = lst_node;
	}
	sort(all_nodes.begin(), all_nodes.end(), [](int a, int b) {
		return pool[a].len < pool[b].len;
	});
	LoopR (i,1,all_nodes.size()) {
		int t = all_nodes[i];
		pool[pool[t].link].cnt += pool[t].cnt;
	}
}

void find_palin(int i)
{
	int j = i-1;
	while (longest_palin[j] == i || s[i-longest_palin[j]-1] != s[i]) {
		if (!second_longest[j]) {
			longest_palin[i] = 1 + (s[i] == s[i-1]);
			second_longest[i] = s[i] == s[i-1];
			return;
		}
		int k = second_longest[j];
		while(longest_palin[j] != k)
			j = j-longest_palin[j]+second_longest[j];
	}
	longest_palin[i] = longest_palin[j]+2;
	do {
		if (!second_longest[j]) {
			second_longest[i] = 1 + (s[i] == s[i-1]);
			return;
		}
		int k = second_longest[j];
		while(longest_palin[j] != k)
			j = j-longest_palin[j]+second_longest[j];
	} while (longest_palin[j] == i || s[i-longest_palin[j]-1] != s[i]);
	second_longest[i] = longest_palin[j]+2;
}

void find_all_palins()
{
	longest_palin[0] = 1;
	second_longest[0] = 0;
	Loop (i,1,n) {
		find_palin(i);
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> s;
	n = s.size();
	make_automata();
	find_all_palins();
	ll ans = 0;
	Loop (i,0,n) {
		int t = index2node[i];
		while (pool[pool[t].link].len >= longest_palin[i]) {
			pool[t].vis = 1;
			t = pool[t].link;
			if (pool[t].vis)
				break;
		}
		if (pool[t].vis)
			continue;
		ans = max(ans, (ll)longest_palin[i] * pool[t].cnt);
	}
	cout << ans << '\n';
}

Compilation message (stderr)

palindrome.cpp: In function 'void insert_node(char)':
palindrome.cpp:44:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |   if (!pool[cur].next[c]) {
      |                       ^
palindrome.cpp:45:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |    pool[cur].next[c] = new_node;
      |                   ^
palindrome.cpp:55:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |  int q = pool[cur].next[c];
      |                         ^
palindrome.cpp:66:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |  while (cur && pool[cur].next[c] == q) {
      |                               ^
palindrome.cpp:67:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |   pool[cur].next[c] = clone;
      |                  ^

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