Submission #47191

#TimeUsernameProblemLanguageResultExecution timeMemory
47191evenharderPalindromes (APIO14_palindrome)C++11
0 / 100
1078 ms69160 KiB
#include <iostream> #include <ios> #include <algorithm> #include <string> #include <vector> #include <array> #include <stack> const int MAX_N = 600006; std::vector<int> make_sa(const std::string& s) { int n = s.length(); std::vector<int> sa(n), g(n+1), ng(n+1); for(int i=0;i<n;i++) { sa[i] = i; g[i] = s[i]; } g[n] = 0; int lim = std::max(128, n+1); for(int t=1;t<s.length();t<<=1) { auto cmp = [&] (int a, int b) { return g[a] != g[b] ? g[a] < g[b] : g[a+t] < g[b+t]; }; std::vector<int> cnt(lim), ind(lim+1); for(int i=0;i<n;i++) cnt[g[std::min(i+t, n)]]++; for(int i=1;i<lim;i++) cnt[i] += cnt[i-1]; for(int i=n-1;i>=0;i--) ind[--cnt[g[std::min(i+t, n)]]] = i; for(int i=0;i<lim;i++) cnt[i] = 0; for(int i=0;i<n;i++) cnt[g[i]]++; // same as cnt[g[ind[i]]]++ for(int i=1;i<lim;i++) cnt[i] += cnt[i-1]; for(int i=n-1;i>=0;i--) sa[--cnt[g[ind[i]]]] = ind[i]; ng[sa[0]] = 1; for(int i=1;i<n;i++) { ng[sa[i]] = ng[sa[i-1]]; if(cmp(sa[i-1], sa[i])) ng[sa[i]]++; } g = ng; } return sa; } std::vector<int> make_lcp(const std::string& s, const std::vector<int>& sa) { int n = s.length(); std::vector<int> lcp(n+1); std::vector<int> rank(n); for(int i=0;i<n;i++) rank[sa[i]] = i; int len = 0; for(int i=0;i<n;i++) { if(rank[i]) { int j = sa[rank[i]-1]; int len_cap = n - std::max(i,j); while(len < len_cap && s[i+len] == s[j+len]) len++; lcp[rank[i]-1] = len; } if(len) len--; } return lcp; } long long int get_max_area(const std::vector<int>& v) { std::stack<int> sh, sx; int n = v.size(); long long int ans = 0; for(int i=0;i<=n;i++) { int val = i < n ? v[i] : 0; int len = 0; int last_x = i; while(!sh.empty() && sh.top() >= val) { ans = std::max(ans, 1LL * sh.top() * (i-sx.top()+1)); last_x = sx.top(); sh.pop(); sx.pop(); } sh.push(val); sx.push(last_x); } return ans; } std::string make_appended_str(const std::string& s) { std::vector<char> v; for(int i=0;i<=s.length();i++) { v.push_back('_'); if(i != s.length()) v.push_back(s[i]); } return std::string(v.begin(), v.end()); } std::vector<int> manacher(const std::string& s) { std::vector<int> ret(s.length()); int r = -1; int p = -1; for(int i=0;i<s.length();i++) { if(i <= r) ret[i] = std::min(r-i, ret[2*p-i]); while(ret[i]+1 <= i && i+ret[i]+1 < s.length() && s[i-ret[i]-1] == s[i+ret[i]+1]) ret[i]++; if(i + ret[i] > r) r = i + ret[i], p = i; } return ret; } int spl[MAX_N+1]; int sp[20][MAX_N]; void set_sp(std::vector<int>& lcp) { int n = lcp.size(); for(int j=0;j<n;j++) sp[0][j] = lcp[j]; for(int i=1;i<20;i++) { for(int j=1;j<=(1<<i);j++) { if((1<<i)+j <= MAX_N) spl[(1<<i)+j] = i; } } for(int i=0;i<19;i++) { for(int j=0;j<n;j++) { sp[i+1][j] = std::min(sp[i][j], sp[i][std::min(j+(1<<i), n-1)]); } } } long long int solve(std::string& s) { std::string s_ = make_appended_str(s); std::vector<int> sa = make_sa(s_); std::vector<int> rank(sa.size()); for(int i=0;i<sa.size();i++) rank[sa[i]] = i; std::vector<int> lcp = make_lcp(s_, sa); std::vector<int> ma = manacher(s_); set_sp(lcp); auto lcp_val = [&] (int x, int y) { x = rank[x]; y = rank[y]; if(x>y) std::swap(x,y); int len = y-x; int res = std::min(sp[spl[len]][x], sp[spl[len]][y-(1<<spl[len])]); return res; }; auto cmp = [&] (int x, int y) { int len = y-x+ 1; int clen = std::min({lcp_val(x,y), ma[x]+1, ma[y]+1}); char chx = clen != ma[x]+1 && x+clen < s_.length() ? s_[x+clen] : 0; char chy = clen != ma[y]+1 && y+clen < s_.length() ? s_[y+clen] : 0; return (chx != chy ? chx < chy : x<y); }; std::vector<int> ord(s_.length()); for(int i=0;i<s_.length();i++) ord[i] = i; std::sort(ord.begin(), ord.end(), cmp); std::vector<int> lcp_palin; for(int i=1;i<ord.size();i++) { int v = std::min({ ma[ord[i-1]], ma[ord[i]], lcp_val(ord[i-1], ord[i])-1}); lcp_palin.push_back(std::max(v,0)); } return get_max_area(lcp_palin); } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::string s; std::cin >> s; std::cout << std::max(solve(s), (long long int)s.length()); }

Compilation message (stderr)

palindrome.cpp: In function 'std::vector<int> make_sa(const string&)':
palindrome.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int t=1;t<s.length();t<<=1)
                 ~^~~~~~~~~~~
palindrome.cpp: In function 'long long int get_max_area(const std::vector<int>&)':
palindrome.cpp:83:13: warning: unused variable 'len' [-Wunused-variable]
         int len = 0;
             ^~~
palindrome.cpp: In function 'std::__cxx11::string make_appended_str(const string&)':
palindrome.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<=s.length();i++)
                 ~^~~~~~~~~~~~
palindrome.cpp:103:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i != s.length()) v.push_back(s[i]);
            ~~^~~~~~~~~~~~~
palindrome.cpp: In function 'std::vector<int> manacher(const string&)':
palindrome.cpp:112:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.length();i++)
                 ~^~~~~~~~~~~
palindrome.cpp:115:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ret[i]+1 <= i && i+ret[i]+1 < s.length() &&
                                ~~~~~~~~~~~^~~~~~~~~~~~
palindrome.cpp: In function 'long long int solve(std::__cxx11::string&)':
palindrome.cpp:152:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<sa.size();i++)
                 ~^~~~~~~~~~
palindrome.cpp: In lambda function:
palindrome.cpp:171:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         char chx = clen != ma[x]+1 && x+clen < s_.length() ? s_[x+clen] : 0;
                                       ~~~~~~~^~~~~~~~~~~~~
palindrome.cpp:172:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         char chy = clen != ma[y]+1 && y+clen < s_.length() ? s_[y+clen] : 0;
                                       ~~~~~~~^~~~~~~~~~~~~
palindrome.cpp:169:13: warning: unused variable 'len' [-Wunused-variable]
         int len = y-x+ 1;
             ^~~
palindrome.cpp: In function 'long long int solve(std::__cxx11::string&)':
palindrome.cpp:176:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s_.length();i++)
                 ~^~~~~~~~~~~~
palindrome.cpp:182:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<ord.size();i++)
                 ~^~~~~~~~~~~
#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...