Submission #552080

#	Time	Username	Problem	Language	Result	Execution time	Memory
552080		QwertyPi	Palindromes (APIO14_palindrome)	C++14	0 / 100	1080 ms	4720 KiB

palindrome

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;
typedef pair<int, int> pii;
const int N = 1e5+1;

const int MOD1 = 1000000007,
		  MOD2 =  999999937;
const int 	a1 =  235829684,
			a2 =  398593609;
int pm(int a, int b, int mod){
	if(b == 0) return 1;
	return pm(a * a % mod, b / 2, mod) * (b % 2 ? a : 1) % mod;
}

int mi(int a, int mod){
	return pm(a, mod - 2, mod);
}

struct StrHash{
	int ha[N], a, p;
	void prec(string& s, int a, int p){
		StrHash::a = a;
		StrHash::p = p;
		for(int i = 0; i < s.size(); i++){
			ha[i + 1] = (ha[i] * a + s[i]) % p;
		}
	}
	
	int hash(int l, int r){
		int ret = ha[r + 1] - ha[l] * pm(a, r - l + 1, p); 
		return (ret % p + p) % p;
	}
} hpf[2], hsf[2];

int32_t main(){
	string s;
	cin >> s;
	int n = s.size();
	vector<tuple<int, int, int>> hashs;
	hpf[0].prec(s, a1, MOD1); hpf[1].prec(s, a2, MOD2);
	reverse(s.begin(), s.end());
	hsf[0].prec(s, a1, MOD1); hsf[1].prec(s, a2, MOD2);
	for(int i = 0; i < n; i++){
		for(int j = i; j < n; j++){
			if(hpf[0].hash(i, j) == hsf[0].hash(i, j) && hpf[1].hash(i, j) == hsf[1].hash(i, j)){
				hashs.push_back({hpf[0].hash(i, j), hpf[1].hash(i, j), j - i + 1});
			}
		}
	}
	sort(hashs.begin(), hashs.end());
	int h1 = 0, h2 = 0, cnt = 0, len = 0, ans = 0;
	for(auto i : hashs){
		if(get<0>(i) != h1 || get<1>(i) != h2){
			h1 = get<0>(i), h2 = get<1>(i);
			cnt = 1, len = get<2>(i), ans = max(ans, cnt * len);
		}else{
			cnt++;
			ans = max(ans, cnt * len);
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

palindrome.cpp: In member function 'void StrHash::prec(std::string&, long long int, long long int)':
palindrome.cpp:28:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i = 0; i < s.size(); i++){
      |                  ~~^~~~~~~~~~

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