Submission #101379

#	Time	Username	Problem	Language	Result	Execution time	Memory
101379		KCSC	Palindromes (APIO14_palindrome)	C++14	0 / 100	3 ms	384 KiB

palindrome

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

class Eertree {

private:

	struct Node {
		map<char, int> son; 
		int length, suffixLink, start, end, psm = 0;
		vector<int> lnk;

		Node(int _length = 0, int _start = 0, int _end = 0) :
			length(_length), suffixLink(0), start(_start), end(_end) {} 
	};

	int last;
	vector<Node> tree; 
	string myString;

	void _addLetter(char ch) {
		int idx = myString.length(), tmp = last;
		myString.push_back(ch);		
		while (true) {
			int len = tree[tmp].length;
			if (idx - len and myString[idx - len - 1] == myString[idx]) {
				break; }
			tmp = tree[tmp].suffixLink; }
		if (tree[tmp].son.find(ch) != tree[tmp].son.end()) {
			last = tree[tmp].son[ch];
			return; }
		tree.push_back(Node(tree[tmp].length + 2, idx - tree[tmp].length - 1, idx));
		last = tree[tmp].son[ch] = tree.size() - 1; tmp = tree[tmp].suffixLink;
		if (tree[last].length == 1) {
			tree[last].suffixLink = 1;
			tree[1].lnk.push_back(last);
			return; }
		while (true) {
			int len = tree[tmp].length;
			if (idx - len and myString[idx - len - 1] == myString[idx]) {
				break; }
			tmp = tree[tmp].suffixLink; }
		tree[last].suffixLink = tree[tmp].son[ch]; tree[tree[tmp].son[ch]].lnk.push_back(last);
		return; }

	void dfs(int x, long long &ans) {
		for (int y : tree[x].lnk) {
			dfs(y, ans); tree[x].psm += tree[y].psm; }
		ans = max(ans, 1LL * (tree[x].end - tree[x].start + 1) * tree[x].psm); }

public:

	Eertree() : last(0) {
		tree.push_back(Node(-1)); 
		tree.push_back(Node( 0)); }

	Eertree(const string str) : last(0) {
		tree.push_back(Node(-1));
		tree.push_back(Node( 0));
		for (char ch : str) {
			_addLetter(ch); } }

	void addLetter(const char ch) {
		_addLetter(ch); }

	void addString(const string str) {
 		for (char ch : str) {
			_addLetter(ch); } }

	void debug(const string str) {
		for (char ch : str) {
			_addLetter(ch); ++tree[last].psm; }
		long long ans = 0; dfs(0, ans); dfs(1, ans);
		cout << tree.size() - 2 << endl;
		for (int i = 2; i < tree.size(); ++i) {
			for (int j = tree[i].start; j <= tree[i].end; ++j) {
				cout << myString[j]; }
			cout << " " << tree[i].psm << endl; } }

	long long solve(const string str) {
		tree[0].lnk.push_back(1);
		for (char ch : str) {
			_addLetter(ch); ++tree[last].psm; }
		long long ans = 0; dfs(0, ans);
		return ans; }

} myEertree;

int main(void) {
	freopen("palindrome.in", "r", stdin);
	freopen("palindrome.out", "w", stdout);
	string str; cin >> str; 
	cout << myEertree.solve(str);
	return 0; }

Compilation message (stderr)

palindrome.cpp: In member function 'void Eertree::debug(std::__cxx11::string)':
palindrome.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 2; i < tree.size(); ++i) {
                   ~~^~~~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:90:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("palindrome.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:91:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("palindrome.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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