/*
* 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 = long long;
//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;
}
Compilation message
sequence.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<T>&)':
sequence.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
sequence.cpp:63:5: note: in expansion of macro 'list'
63 | list(i, SZ(v)) {
| ^~~~
sequence.cpp: In member function 'void StringHash::init(const string&)':
sequence.cpp:23:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
sequence.cpp:129:9: note: in expansion of macro 'list'
129 | list(k, 2) {
| ^~~~
sequence.cpp:22:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
| ^
sequence.cpp:132:13: note: in expansion of macro 'rep'
132 | rep(i, 1, n + 1) {
| ^~~
sequence.cpp:23:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
sequence.cpp:139:9: note: in expansion of macro 'list'
139 | list(k, 2) {
| ^~~~
sequence.cpp:22:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
| ^
sequence.cpp:142:13: note: in expansion of macro 'rep'
142 | rep(i, 2, n + 1) {
| ^~~
sequence.cpp: In member function 'std::vector<long long int> StringHash::get(int, int)':
sequence.cpp:23:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
sequence.cpp:152:9: note: in expansion of macro 'list'
152 | list(k, 2) {
| ^~~~
sequence.cpp: In function 'int32_t main()':
sequence.cpp:22:31: warning: unnecessary parentheses in declaration of 'len' [-Wparentheses]
22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
| ^
sequence.cpp:186:5: note: in expansion of macro 'rep'
186 | rep(len, 1, n + 1){
| ^~~
sequence.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
sequence.cpp:188:9: note: in expansion of macro 'list'
188 | list(i, n - len + 1){
| ^~~~
sequence.cpp:28:30: warning: unnecessary parentheses in declaration of 'c' [-Wparentheses]
28 | #define trav(a, x) for(auto& (a): (x))
| ^
sequence.cpp:194:9: note: in expansion of macro 'trav'
194 | trav(c, cnt){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
424 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
