제출 #42025

#제출 시각아이디문제언어결과실행 시간메모리
42025Aidyn_A회문 (APIO14_palindrome)C++14
23 / 100
1054 ms51560 KiB
#include <stdio.h>
#include <bits/stdc++.h>			

#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = (int)1e4 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;
const int P = 31;

int mult(int a, int b) {
	return 1ll * a * b % MOD;
}

int add(int a, int b) {
	a += b;
	if(a >= MOD) a -= MOD;
	return a;
}

int subs(int a, int b) {
	a -= b;
	if(a < 0) a += MOD;
	return a;
}

string s;
unordered_map<int, int> cnt;
int pw[N];
int h[N];

int get_hash(int l, int r) {
	return subs(h[r], mult(h[l - 1], pw[r - l + 1]));
}

int main() {
	pw[0] = 1;
	for(int i = 1; i <= N - 123; i ++)
		pw[i] = mult(pw[i - 1], P);
	cin >> s;
	cnt.reserve(sz(s) * 10);
	h[0] = s[0];
	for(int i = 1; i < sz(s); i ++)
		h[i] = add(mult(h[i - 1], P), s[i]);	
	ll res = 0;
	for(int i = 0; i < sz(s); i ++) {
		int len = 1;
		cnt[s[i]] ++;
		while(i - len >= 0 && i + len < sz(s) && s[i - len] == s[i + len]) {
			cnt[get_hash(i - len, i + len)] ++;
			len ++;
		}
	}
	for(int i = 0; i < sz(s); i ++) {
		int len = 1;
		res = max(res, 1ll * cnt[s[i]]);
		while(i - len >= 0 && i + len < sz(s) && s[i - len] == s[i + len]) {
			res = max(res, 1ll * (len * 2 + 1) * cnt[get_hash(i - len, i + len)]);
			len ++;
		}
	}
	//_____________________________________________
	for(int i = 0; i < sz(s); i ++) {
		int len = 0;
		while(i - len - 1 >= 0 && i + len < sz(s) && s[i - len - 1] == s[i + len]) {
			cnt[get_hash(i - len - 1, i + len)] ++;
			len ++;
		}
	}
	for(int i = 0; i < sz(s); i ++) {
		int len = 0;
		while(i - len - 1 >= 0 && i + len < sz(s) && s[i - len - 1] == s[i + len]) {
			res = max(res, 1ll * (len + 1) * 2 * cnt[get_hash(i - len - 1, i + len)]);
			len ++;
		}
	}
	cout << res;
	return 0;  
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...