結果

問題 No.765 ukuku 2
コンテスト
ユーザー rickytheta
提出日時 2018-12-13 00:56:34
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 134 ms / 3,000 ms
コード長 3,653 bytes
コンパイル時間 1,624 ms
コンパイル使用メモリ 163,104 KB
実行使用メモリ 7,112 KB
最終ジャッジ日時 2024-09-25 03:54:13
合計ジャッジ時間 5,168 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:28:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |   scanf("%s",s);
      |   ~~~~~^~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

// const ll B = 10007;
const ll B = 10007;
const ll MOD = 1000000009;
int bpow[252521];

int n;
char s[252521];
char rs[252521];
int hsh[252521], rhsh[252521];

int rhash(int *h, int l, int r){
  // s[l,...,r-1]
  return (h[r] - (ll)h[l]*bpow[r-l]%MOD + MOD) % MOD;
}

int main(){
  scanf("%s",s);
  n = strlen(s);
  REP(i,n)rs[n-1-i] = s[i];
  REP(i,n)hsh[i+1] = ((ll)hsh[i]*B + s[i]) % MOD;
  REP(i,n)rhsh[i+1] = ((ll)rhsh[i]*B + rs[i]) % MOD;
  bpow[0] = 1;
  FOR(i,1,252521)bpow[i] = (ll)bpow[i-1]*B%MOD;

  int ans = 1;
  // center character is s[i]
  REP(i,n){
    // no remove
    int low = 0, high = min(i, n-1-i)+1;
    while(low+1<high){
      int len = (low+high)/2;
      int lefthash = rhash(hsh, i-len, i);
      int righthash = rhash(rhsh, n-1-len-i, n-i-1);
      if(lefthash == righthash){
        low = len;
      }else{
        high = len;
      }
    }
    int clen = low;
    CHMAX(ans, 2*clen);  // remove center character
    if(2*clen+1 < n)CHMAX(ans, 2*clen+1); // remove other character
    // remove left
    if(i-clen > 0){
      int l = i-clen-1;
      int r = i+clen;
      int low = 0, high = min(l, n-1-r)+1;
      while(low+1<high){
        int len = (low+high)/2;
        int lefthash = rhash(hsh, l-len, l);
        int righthash = rhash(rhsh, n-1-len-r, n-r-1);
        if(lefthash == righthash){
          low = len;
        }else{
          high = len;
        }
      }
      CHMAX(ans, 2*clen+2*low+1);
    }
    // remove right
    if(i+clen < n-1){
      int l = i-clen;
      int r = i+clen+1;
      int low = 0, high = min(l, n-1-r)+1;
      while(low+1<high){
        int len = (low+high)/2;
        int lefthash = rhash(hsh, l-len, l);
        int righthash = rhash(rhsh, n-1-len-r, n-r-1);
        if(lefthash == righthash){
          low = len;
        }else{
          high = len;
        }
      }
      CHMAX(ans, 2*clen+2*low+1);
    }
  }
  // center character is s[i], s[i+1]
  REP(i,n-1)if(s[i]==s[i+1]){
    // no remove
    int l = i, r = i+1;
    int low = 0, high = min(l, n-1-r)+1;
    while(low+1<high){
      int len = (low+high)/2;
      int lefthash = rhash(hsh, l-len, l);
      int righthash = rhash(rhsh, n-1-len-r, n-r-1);
      if(lefthash == righthash){
        low = len;
      }else{
        high = len;
      }
    }
    int clen = low;
    CHMAX(ans, 2*clen+1);  // remove center character
    if(2*clen+2 < n)CHMAX(ans, 2*clen+2); // remove other character
    // remove left
    if(i-clen > 0){
      int l = i-clen-1;
      int r = i+1+clen;
      int low = 0, high = min(l, n-1-r)+1;
      while(low+1<high){
        int len = (low+high)/2;
        int lefthash = rhash(hsh, l-len, l);
        int righthash = rhash(rhsh, n-1-len-r, n-r-1);
        if(lefthash == righthash){
          low = len;
        }else{
          high = len;
        }
      }
      CHMAX(ans, 2*clen+2+2*low);
    }
    // remove right
    if(i+1+clen < n-1){
      int l = i-clen;
      int r = i+1+clen+1;
      int low = 0, high = min(l, n-1-r)+1;
      while(low+1<high){
        int len = (low+high)/2;
        int lefthash = rhash(hsh, l-len, l);
        int righthash = rhash(rhsh, n-1-len-r, n-r-1);
        if(lefthash == righthash){
          low = len;
        }else{
          high = len;
        }
      }
      CHMAX(ans, 2*clen+2+2*low);
    }
  }
  printf("%d\n",ans);
  return 0;
}
0