Submission #99294

#	Time	Username	Problem	Language	Result	Execution time	Memory
99294		mirbek01	Palindromes (APIO14_palindrome)	C++11	47 / 100	1082 ms	119340 KiB

palindrome

# include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 2;
const int mod = 1e9 + 9;

int n, bor[26][N], cnt[N * 27], used[26], cn = 1;
long long ans, h[N], h1[N], pr = 101, pw[N];
string s;
unordered_map <int, int> mp;

int get(int l, int r){
      long long hs = (h[r] - h[l - 1] + mod) % mod;
      hs = (hs * pw[N - l]) % mod;
      return hs;
}
int get1(int l, int r){
      long long hs = (h1[r] - h1[l - 1] + mod) % mod;
      hs = (hs * pw[N - l]) % mod;
      return hs;
}
void add(int v, int id, int len, int c){
      while(1){
            if(id - len <= 0 || id + len + c > n || s[id - len] != s[id + len + c]){
                  break;
            }
            int now = s[id - len] - 'a';
            if(!bor[now][v]){
                  bor[now][v] = ++ cn;
            }
            v = bor[now][v];
            mp[get(id - len, id)] = v;
            len ++;
      }
      cnt[v] ++;
}
void f(int v, int len, int c){
      for(int i = 0; i < 26; i ++){
            if(bor[i][v]){
                  f(bor[i][v], len + 1, c);
                  cnt[v] += cnt[bor[i][v]];
            }
      }
      ans = max(ans, (len * 2 - c) * 1ll * cnt[v]);
}

int main(){
      cin >> s;
      n = s.size();
      s = ' ' + s;
      pw[0] = pr;
      for(int i = 1; i < N; i ++)
            pw[i] = (pw[i - 1] * pr) % mod;
      for(int i = 1; i <= n; i ++){
            h[i] = (h[i - 1] + (s[i] - 'a' + 1) * pw[i]) % mod;
            h1[i] = (h1[i - 1] + (s[n - i + 1] - 'a' + 1) * pw[i]) % mod;
      }
      for(int i = 1; i <= n; i ++){
            if(!used[s[i] - 'a']){
                  used[s[i] - 'a'] = 1;
                  add(1, i, 0, 0);
                  continue;
            }
            int lo = max(1, i - (n - i)), hi = i, pos;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  int f = get(md, i + (i - md)), s = get1(n - (i + (i - md)) + 1, n - md + 1);
                  if(mp[get(md, i)] && f == s)
                        hi = md - 1, pos = md;
                  else
                        lo = md + 1;
            }
            add(mp[get(pos, i)], i, i - pos + 1, 0);
      }
      f(1, 0, 1);
      memset(bor, 0, sizeof(bor));
      memset(cnt, 0, sizeof(cnt));
      memset(used, 0, sizeof(used));
      cn = 1;
      mp.clear();
      for(int i = 1; i < n; i ++){
            if(s[i] != s[i + 1])
                  continue;
            if(!used[s[i] - 'a']){
                  used[s[i] - 'a'] = 1;
                  add(1, i, 0, 1);
                  continue;
            }
            int lo = max(1, i - (n - i - 1)), hi = i, pos = -1;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  int f = get(md, i + (i - md) + 1), s = get1(n - (i + (i - md) + 1) + 1, n - md + 1);
                  if(mp[get(md, i)] && f == s)
                        hi = md - 1, pos = md;
                  else
                        lo = md + 1;
            }
            add(mp[get(pos, i)], i, i - pos + 1, 1);
      }
      f(1, 0, 0);
      cout << ans << endl;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:15:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
       hs = (hs * pw[N - l]) % mod;
                     ~~^~~
palindrome.cpp:65:51: note: 'pos' was declared here
             int lo = max(1, i - (n - i)), hi = i, pos;
                                                   ^~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27