제출 #99288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99288		mirbek01	회문 (APIO14_palindrome)	C++11	0 / 100	980 ms	132096 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], pr = 101, pw[N];
string s;
unordered_map <int, int> mp;

int get(int l, int r){
      long long hs = (h[r] - h[l] + mod) % mod;
      hs = (hs * pw[N - l]) % mod;
      return hs;
}
void add(int v, int id, int len, int c){
      for(; len < min(n - id + 1, id); len ++){
            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;
      }
      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;
      }
      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;
                  if(mp[get(md, i)])
                        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;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(mp[get(md, i)])
                        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;
}

컴파일 시 표준 에러 (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:82:55: note: 'pos' was declared here
             int lo = max(1, i - (n - i - 1)), hi = i, pos;
                                                       ^~~
palindrome.cpp:15:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
       hs = (hs * pw[N - l]) % mod;
                     ~~^~~
palindrome.cpp:58:51: note: 'pos' was declared here
             int lo = max(1, i - (n - i)), hi = i, pos;
                                                   ^~~

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