| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 562872 | beep_boop | 수열 (APIO14_sequence) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
* Created at 5:39 PM on 15 May, 2022
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <numeric>
#include <cassert>
#include <functional>
using namespace std;
#define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
#define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SZ(x) (int)(x).size()
#define vt vector
#define trav(a, x) for(auto& (a): (x))
#define DO if(true)
#define mp make_pair
#define pb push_back
#define eb emplace_back
//#define int int64_t
typedef vector<int> vi;
typedef pair<int, int> pi;
#define mod 1000000007
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
template<typename T>
void read(vector<T> &a, int n) {
a.resize(n);
for (auto &x: a) cin >> x;
}
template<class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &v) {
out << "(";
out << v.first << ", " << v.second;
return out << ")";
}
template<class T>
ostream &operator<<(ostream &out, const vector<T> &v) {
out << "[";
list(i, SZ(v)) {
if (i) out << ", ";
out << v[i];
}
return out << "]";
}
template<typename T>
void print(vector<T> &a) {
for (const auto &x: a) cout << x << ' ';
cout << '\n';
}
template<typename T>
void MOD(T &x, int m = mod) {
x %= m;
if (x < 0) x += m;
}
#define trace(...) dbg(#__VA_ARGS__, __VA_ARGS__)
template<typename T>
void dbg(const char *name, T &&arg1) {
cout << name << " : " << arg1 << '\n';
}
template<typename T, typename... U>
void dbg(const char *names, T &&arg1, U &&... args) {
const char *comma = strchr(names + 1, ',');
cout.write(names, comma - names) << " : " << arg1 << " | ";
dbg(comma + 1, args...);
}
template<class T>
void read(T &x) {
cin >> x;
}
template<class T, class... U>
void read(T &t, U &... u) {
read(t);
read(u...);
}
int gcd(int a, int b) { return !a ? b : gcd(b % a, a); }
int ceil_div(int a, int b) { return (a + b - 1) / b; }
using ll = int64_t;
//Rolling Hash for Strings
struct StringHash {
int n = 1;
string s;
//The Hashes
const ll A = 911382323;
const ll M[2] = {999999937, 10620793};
vt<ll> pow[2], pref[2];
void init(const string &x) {
s = x;
n = SZ(s);
//Computing the powers of the primes
list(k, 2) {
pow[k].resize(n + 1);
pow[k][0] = 1;
rep(i, 1, n + 1) {
pow[k][i] = A * pow[k][i - 1];
MOD(pow[k][i], M[k]);
}
}
//Computing the prefix sums
list(k, 2) {
pref[k].resize(n + 1, 0);
pref[k][1] = s[0] - 'a';
rep(i, 2, n + 1) {
pref[k][i] = pref[k][i - 1] * A + (s[i - 1] - 'a');
MOD(pref[k][i], M[k]);
}
}
}
//returns the hash of [l, r)
vt<ll> get(int l, int r) {
vt<ll> res(2);
list(k, 2) {
res[k] = pref[k][r] - (pref[k][l] * pow[k][r - l]);
MOD(res[k], M[k]);
}
return res;
}
//Checks if [l, r) is equal to [x, y)
bool equal(int l, int r, int x, int y) {
return get(l, r) == get(x, y);
}
};
const int N = 1002;
int n;
string s;
int32_t main() {
setIO();
read(s);
n = SZ(s);
string t = s;
reverse(ALL(t));
StringHash st;
st.init(s);
StringHash ts;
ts.init(t);
ll ans = 0;
rep(len, 1, n + 1){
map<vt<ll>, int> cnt;
list(i, n - len + 1){
if(st.get(i, i + len) == ts.get(i, i + len)){
cnt[st.get(i, i + len)]++;
}
}
trav(c, cnt){
ans = max(ans, len * 1LL * c.second);
}
}
cout << ans << '\n';
return 0;
}