#138859 (C++11) No.464 PPAP

• 問題: No.464 PPAP
• ユーザー: koba-e964
• 提出日時: 2016-12-15 23:18:19
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 478 ms / 2,000 ms
• コード長: 3,802 bytes
• コンパイル時間: 963 ms
• コンパイル使用メモリ: 73,448 KB
• 実行使用メモリ: 70,912 KB
• 最終ジャッジ日時: 2024-11-30 08:59:38
• 合計ジャッジ時間: 4,758 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	16 ms; 9,600 KB
testcase_08	AC	16 ms; 9,600 KB
testcase_09	AC	17 ms; 9,600 KB
testcase_10	AC	338 ms; 70,784 KB
testcase_11	AC	229 ms; 51,200 KB
testcase_12	AC	334 ms; 70,784 KB
testcase_13	AC	352 ms; 70,784 KB
testcase_14	AC	354 ms; 70,784 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	2 ms; 5,248 KB
testcase_17	AC	2 ms; 5,248 KB
testcase_18	AC	2 ms; 5,248 KB
testcase_19	AC	2 ms; 5,248 KB
testcase_20	AC	3 ms; 5,248 KB
testcase_21	AC	2 ms; 5,248 KB
testcase_22	AC	3 ms; 5,248 KB
testcase_23	AC	478 ms; 70,784 KB
testcase_24	AC	423 ms; 70,784 KB
testcase_25	AC	406 ms; 70,912 KB

ソースコード

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

/*
 * Suffix Array.
 * Required Headers: algorithm, cassert, string, vector
 * Verified by: http://arc050.contest.atcoder.jp/submissions/818745
 * Reference: http://mayokoex.hatenablog.com/entry/2016/04/03/145845
 */
struct compare_sa {
  const std::vector<int> &rank;
  int n, k;
  compare_sa(const std::vector<int> &rank, int n, int k) : rank(rank), n(n), k(k) {}
  bool operator () (int i, int j) {
    if (rank[i] != rank[j]) {
      return rank[i] < rank[j];
    }
    int ri = i + k <= n ? rank[i + k] : -1;
    int rj = j + k <= n ? rank[j + k] : -1;
    return ri < rj;
  }
};

std::vector<int> create_sa(const std::string& s) {
  int n = s.length();
  std::vector<int> sa(n + 1, -1);
  std::vector<int> rank(n + 1, -1);
  std::vector<int> tmp(n + 1, -1);
  
  for (int i = 0; i <= n; ++i) {
    sa[i] = i;
    rank[i] = i < n ? s[i] : -1;
  }
  
  for (int k = 1; k <= n; k *= 2) {
    compare_sa cp = compare_sa(rank, n, k);
    std::sort(sa.begin(), sa.begin() + n + 1, cp);
    tmp[sa[0]] = 0;
    for (int i = 1; i <= n; ++i) {
      tmp[sa[i]] = tmp[sa[i - 1]] + (cp(sa[i - 1], sa[i]) ? 1 : 0);
    }
    for (int i = 0; i <= n; ++i) {
      rank[i] = tmp[i];
    }
  }
  return sa;
}

std::vector<int> create_lcp(const std::string &s, const std::vector<int> &sa) {
  int n = s.length();
  std::vector<int> rank(n + 1);
  std::vector<int> lcp(n, -1);
  for (int i = 0; i <= n; ++i) {
    rank[sa[i]] = i;
  }
  int h = 0;
  lcp[0] = 0;
  for (int i = 0; i < n; ++i) {
    int j = sa[rank[i] - 1];
    h = std::max(0, h - 1);
    for (; j + h < n && i + h < n; ++h) {
      if (s[j + h] != s[i + h]) {
	break;
      }
    }
    lcp[rank[i] - 1] = h;
  }
  return lcp;
}

std::vector<std::vector<int> > create_sparse_table(int n, const std::vector<int> &lcp) {
  int h = 1;
  while ((1 << h) < n) {
    ++h;
  }
  std::vector<std::vector<int> > st(h + 1, std::vector<int>(n));

  for (int i = 0; i < n; ++i) {
    st[0][i] = lcp[i];
  }
  for (int j = 1; j <= h; ++j) {
    for (int i = 0; i <= n - (1 << j); ++i) {
      st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << (j-1))]);
    }
  }
  return st;
}

int top_bit(int t) {
  for (int i = 31; i >= 0; --i) {
    if ((1 << i) & t) {
      return i;
    }
  }
  assert (0);
}

int get_lcp(const std::vector<std::vector<int> > &st, int f, int s) {
  if (f > s) {
    std::swap(f, s);
  }
  assert (f < s);
  int diff = top_bit(s - f);
  return std::min(st[diff][f], st[diff][s - (1 << diff)]);
}



const int N = 5001;
int pal[N][N];
int pal2[N];

int main(void){
  string s;
  cin >> s;
  string s_rev = s;
  reverse(s_rev.begin(), s_rev.end());
  int n = s.length();
  string t = s + "$" + s_rev;
  VI sa = create_sa(t);
  VI sa_inv(sa.size());
  REP(i, 0, sa.size()) {
    sa_inv[sa[i]] = i;
  }
  VI lcp = create_lcp(t, sa);
  vector<VI> spt = create_sparse_table(2 * n + 1, lcp);
  REP(i, 0, n) {
    REP(j, i, n) {
      int idx1 = sa_inv[i];
      int idx2 = sa_inv[n + 1 + (n - 1 - j)];
      int comm_len = get_lcp(spt, idx1, idx2);
      if (0) {
	cerr << "idx1=" << idx1 << ", idx2=" << idx2 << endl;
	cerr << "lcp(s[" << i << "..], s[.." << j << "].rev) = "
	     << comm_len;
	if (comm_len >= j - i + 1) {
	  cerr << " pal";
	}
	cerr << endl;
      }
      pal[i][j] = comm_len >= j - i + 1;
    }
  }
  REP(i, 0, n) {
    REP(j, 0, n) {
      pal2[j] += pal[0][i] * pal[i + 1][j];
    }
  }
  ll tot = 0;
  REP(i, 0, n) {
    REP(j, i + 2, n) {
      tot += (ll)pal2[i] * pal[j][n - 1];
    }
  }
  cout << tot << endl;
}