이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto& operator <<(auto& o, __int128_t x) {return o<<(long long)x;}
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
struct hashTab
{
const __int128_t MOD = 1000000000000000009;
const __int128_t R = 68601583113456465;
const __int128_t X = 379;
vector<__int128_t> rev;
vector<__int128_t> pot;
vector<__int128_t> hs;
vector<__int128_t> rhs;
int n;
__int128_t mulp(__int128_t a, __int128_t b)
{
return (a * b)%MOD;
}
__int128_t add(__int128_t a, __int128_t b)
{
__int128_t c = a+b;
if(c < 0) c += MOD;
if(c >= MOD) return c - MOD;
return c;
}
hashTab(string s)
{
n = s.size();
rev.resize(n);
rev[0] = R;
pot.resize(n);
pot[0] = X;
hs.resize(n);
rhs.resize(n);
for(int i=1;i<n;i++)
pot[i] = mulp(pot[i-1], X), rev[i] = mulp(rev[i-1], R);
for(int i=0;i<n;i++)
hs[i] = add(mulp((s[i]), pot[i]), (i > 0 ? hs[i-1] : 0)),
rhs[i] = add(mulp((s[i]), pot[n-i-1]), (i > 0 ? rhs[i-1] : 0));
debug(hs);
debug(rhs);
}
__int128_t get(int x, int y, bool f)
{
assert(x >= 0 && y < hs.size() && x <= y);
if(!f)
return mulp(add(hs[y], -(x > 0 ? hs[x-1] : 0)), (x > 0 ? rev[x-1] : 1));
return mulp(add(rhs[y], -(x > 0 ? rhs[x-1] : 0)), (y < n-1 ? rev[n - (y+1) - 1] : 1));
}
};
vector<pair<int, int> > getIdx(string s)
{
string t;
for(auto v : s)
t += string("#") + v;
s = t+"#";
debug(s);
hashTab A(s);
set<pair<__int128_t, pair<int, int> > > idx;
auto check = [&](int x, int r)
{
if(x - r < 0) return false;
if(x + r >= s.size()) return false;
debug(x-r);
debug(x+r);
debug(A.get(x-r, x, 0));
debug(A.get(x, x+r, 1));
if(A.get(x-r, x, 0) == A.get(x, x+r, 1))
if(idx.lower_bound(make_pair(A.get(x-r, x+r, 0), make_pair(-1, -1)))->first != A.get(x-r, x+r, 0))
return true;
return false;
};
for(int i=s.size()-1;i>=0;i--)
{
debug(i);
int p = -1, q = s.size();
while(p != q-1)
{
int pol = (p+q) >> 1;
if(check(i, pol))
p = pol;
else
q = pol;
}
debug(q);
for(int j=0;j<q;j++)
idx.insert(make_pair(A.get(i - j, i + j, 0), make_pair(i - j, j*2+1)));
}
vector<pair<int, int> > res;
for(auto v : idx)
if(v.second.first%2 == 1)
{
if(s[v.second.first + v.second.second] == '#')
res.push_back({v.second.first/2, (v.second.second+1)/2});
else
res.push_back({v.second.first/2, v.second.second/2});
}
return res;
}
struct sufAr
{
int n;
vector<int> cntSort;//[n+1]
vector<int> order;//[n]
vector<int> rank;
vector<int> cp;
vector<int> pt;
void layerCompute(int k)//rank: i -> (1..n)
{
// debug(order);
// debug(rank);
if((1<<(k-1)) > n) return;
auto Fill = [&](vector<int>& O, bool f)
{
fill(pt.begin(), pt.end(), -1);
int p = f ? (1<<(k-1)) : 0;
for(auto i : O)
{
int x = 0;
if(i + p < n) x = rank[i+p];
pt[i] = cntSort[x];
cntSort[x] = i;
}
};
auto Sort = [&](vector<int>& O)
{
O.clear();
vector<int> q;
for(int i=0;i<=n;i++)
{
while(cntSort[i] != -1)
{q.push_back(cntSort[i]); cntSort[i] = pt[cntSort[i]];}
while(q.size())
{O.push_back(q.back()); q.pop_back();}
}
};
for(int i=0;i<n;i++) order[i] = i;
Fill(order, 1);
Sort(order);
debug(order);
Fill(order, 0);
Sort(order);
int cnt = 1;
cp = rank;
rank[order[0]] = cnt++;
for(int i=1;i<n;i++)
{
if(cp[order[i]] == cp[order[i-1]])
{
int a = (order[i] + (1<<(k-1)) < n) ? cp[order[i] + (1<<(k-1))] : 0;
int b = (order[i-1] + (1<<(k-1)) < n) ? cp[order[i-1] + (1<<(k-1))] : 0;
if(a == b) {rank[order[i]] = rank[order[i-1]]; continue;}
}
rank[order[i]] = cnt++;
}
layerCompute(k+1);
}
vector<int> LCP;
void lcpCnt(string s)
{
LCP.resize(n-1);
int k = 0;
for(auto& v : rank) --v;
for(int i=0;i<n;i++)
{
if(rank[i] == n-1){k = 0; continue;}
int j = order[rank[i] + 1];
while(i + k < n && j + k < n && s[i+k] == s[j+k])
k++;
LCP[rank[i]] = k;
if(k) k--;
}
}
sufAr(string s)
{
n = s.size();
pt.resize(n+1);
cntSort.resize(n+1, -1);
for(int i=0;i<n;i++) order.push_back(i);
sort(order.begin(), order.end(), [&](int a, int b){
return s[a] < s[b];
});
rank.resize(n);
int cnt = 1;
rank[order[0]] = cnt++;
for(int i=1;i<n;i++)
if(s[order[i]] == s[order[i-1]])
rank[order[i]] = rank[order[i-1]];
else
rank[order[i]] = cnt++;
layerCompute(1);
lcpCnt(s);
// debug(order);
// debug(LCP);
}
};
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin>>s;
vector<pair<int, int> > pals = getIdx(s);
debug(pals);
sufAr A(s);
long long res = 0;
for(auto v : pals)
{
int ans = 1;
int r = A.rank[v.first];
while(r >= 0 && A.LCP[r] >= v.second)
r--;
r++;
while(r < A.LCP.size() && A.LCP[r] >= v.second)
ans++, r++;
res = max(res, (long long)ans*(long long)v.second);
}
cout<<res;
}
컴파일 시 표준 에러 (stderr) 메시지
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from palindrome.cpp:1:
palindrome.cpp: In member function '__int128 hashTab::get(int, int, bool)':
palindrome.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<__int128>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | assert(x >= 0 && y < hs.size() && x <= y);
| ~~^~~~~~~~~~~
palindrome.cpp: In lambda function:
palindrome.cpp:69:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | if(x + r >= s.size()) return false;
| ~~~~~~^~~~~~~~~~~
palindrome.cpp: In function 'int32_t main()':
palindrome.cpp:221:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
221 | while(r < A.LCP.size() && A.LCP[r] >= v.second)
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |