Submission #648688

#	Time	Username	Problem	Language	Result	Execution time	Memory
648688		ymm	Palindromes (APIO14_palindrome)	C++17	73 / 100	90 ms	131072 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 {
	node *link = 0;
	node *next[alpha] = {};
	int len = 0;
	int cnt = 0;
	bool vis = 0;
} rt;

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

node *index2node[N];

void make_automata()
{
	Loop (i,0,n) {
		insert_node(s[i]);
		index2node[i] = lst_node;
	}
	sort(all_nodes.begin(), all_nodes.end(), [](node *a, node *b) {
		return a->len < b->len;
	});
	LoopR (i,1,all_nodes.size()) {
		node *t = all_nodes[i];
		t->link->cnt += 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) {
		node *t = index2node[i];
		while (t->link->len >= longest_palin[i]) {
			t->vis = 1;
			t = t->link;
			if (t->vis)
				break;
		}
		if (t->vis)
			continue;
		ans = max(ans, (ll)longest_palin[i] * t->cnt);
	}
	cout << ans << '\n';
}

Compilation message (stderr)

palindrome.cpp: In function 'void insert_node(char)':
palindrome.cpp:36:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   36 |   if (!cur->next[c]) {
      |                  ^
palindrome.cpp:37:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |    cur->next[c] = new_node;
      |              ^
palindrome.cpp:47:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   47 |  node *q = cur->next[c];
      |                      ^
palindrome.cpp:58:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |  while (cur && cur->next[c] == q) {
      |                          ^
palindrome.cpp:59:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |   cur->next[c] = clone;
      |             ^

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