Submission #493451

#	Time	Username	Problem	Language	Result	Execution time	Memory
493451		Bogdan1110	Palindromes (APIO14_palindrome)	C++17	100 / 100	65 ms	62316 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

string s;

struct PalTree {
	struct Node {
		int cnt;
		int len;
		int dub;
		int slink;
		int to[26];
		Node() { 
			len = dub = cnt = slink = 0; 
			for (int i = 0; i < 26 ; i++ ) to[i] = 0;
		}
		Node( int _len, int _dub, int _cnt, int _slink) {
			len = _len;
			dub = _dub;
			cnt = _cnt;
			slink = _slink;
			for (int i = 0 ; i < 26 ; i++ ) to[i] = 0;
		}
	};
	vector<Node>vec;
	int suff = 2;
	
	void AddNode( int i ) {
		while(i - 1 - vec[suff].len < 0 ||  s[i]!= s[i-vec[suff].len-1] ) {
			suff = vec[suff].slink;
		}
		//cout << i << ' ' << suff << "    ";
		int gde=  s[i]-'a';
		int cvor = vec[suff].to[gde];
		if ( vec[suff].to[gde] == 0 ) {
			vec[suff].to[gde] = vec.size();
			cvor = vec.size();
			vec.push_back(Node(vec[suff].len+2, vec[suff].dub+1, 0, suff));
			if ( suff == 1 ) {
				vec[cvor].slink = 2;
			}
			else {
				suff = vec[suff].slink;
				while(i - 1 - vec[suff].len < 0 ||  s[i- vec[suff].len -1] != s[i] ) {
					suff = vec[suff].slink;
				}
				vec[cvor].slink = vec[suff].to[gde];
			}
			vec[cvor].dub = vec[vec[cvor].slink].dub + 1;
		}
		suff = cvor;
		vec[cvor].cnt++;
		//cout << i <<  ' ' << vec[suff].len <<  ' ' << vec[suff].slink << ' ' << suff << endl;
	} 
	
	void Init() {
		vec.clear();
		suff = 2;
		vec.push_back(Node(0,0,0,0));
		vec.push_back(Node(-1,0,0,1));
		vec.push_back(Node(0,0,0,1));
	}
	
	void CalcCnt() {
		for (int i = vec.size()-1 ; i >= 2  ; i-- ) {
			vec[vec[i].slink].cnt += vec[i].cnt;
		}
	}
	
};
PalTree pt;
int main () {
	cin >> s;
	int n = s.length();
	pt.Init();
	for ( int i = 0 ; i < n ; i++ ) {
		pt.AddNode(i);
	}
	pt.CalcCnt();
	long long rez = 0;
	for (int i = 0 ; i < pt.vec.size(); i++ ) {
		rez = max(rez, (long long)pt.vec[i].len * pt.vec[i].cnt);
		//cout << pt.vec[i].len << ' ' << pt.vec[i].cnt << endl ;
	}
	cout << rez << endl ;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PalTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for (int i = 0 ; i < pt.vec.size(); i++ ) {
      |                   ~~^~~~~~~~~~~~~~~

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