結果

問題 No.263 Common Palindromes Extra
ユーザー y_mazuny_mazun
提出日時 2015-08-31 22:31:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 87 ms / 2,000 ms
コード長 4,051 bytes
コンパイル時間 723 ms
コンパイル使用メモリ 72,664 KB
実行使用メモリ 104,232 KB
最終ジャッジ日時 2023-08-20 00:34:24
合計ジャッジ時間 2,020 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
4,952 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 12 ms
7,928 KB
testcase_04 AC 48 ms
26,624 KB
testcase_05 AC 43 ms
26,332 KB
testcase_06 AC 6 ms
5,528 KB
testcase_07 AC 63 ms
46,996 KB
testcase_08 AC 60 ms
46,872 KB
testcase_09 AC 75 ms
65,144 KB
testcase_10 AC 87 ms
104,232 KB
testcase_11 AC 40 ms
26,104 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstring>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>

using namespace std;

template<typename C, typename C::value_type low, typename C::value_type high, int bit = 32>
class PalindromeTree{
  const static int m = high - low + 1;
  const static int b = (m * bit + 31) / 32;

  typedef typename C::value_type T;

  struct node{
    int next_[b];
    int len;
    int sufflink;

    int next(int i){
      const int bs = i * bit;
      const int be = i * bit + bit;

      const int ys = bs / 32;
      const int sc = min(bit, 32 - (bs % 32));
      const int ye = be / 32;
      const int ec = bit - sc;

      int ret = 0;
      ret |= (next_[ys] >> (bs % 32)) & ((1ll << sc) - 1);
      if(ec != 0) ret |= (next_[ye] & ((1ll << ec) - 1)) << sc;

      return ret;
    }

    void next(int i, int v){
      const int bs = i * bit;
      const int be = i * bit + bit;

      const int ys = bs / 32;
      const int sc = min(bit, 32 - (bs % 32));
      const int ye = be / 32;
      const int ec = bit - sc;

      next_[ys] &= ~(((1ll << sc) - 1) << (bs % 32));
      next_[ys] |= (v & ((1ll << sc) - 1)) << (bs % 32);

      if(ec != 0) next_[ye] &= ~((1ll << ec) - 1);
      if(ec != 0) next_[ye] |= (v >> sc) & ((1ll << ec) - 1);
    }
  };

  const C s;
  int len;
  int num;

  void initTree(){
    num = 2; suff = 2;
    tree[1].len = -1; tree[1].sufflink = 1;
    tree[2].len = 0; tree[2].sufflink = 1;
  }

public:
  node *tree;
  int suff;

  bool addLetter(int pos){
    int cur = suff;
    int curLen = 0;
    const int let = s[pos] - low;

    while(true){
      curLen = tree[cur].len;
      if(pos - 1 - curLen >= 0 && s[pos - 1 - curLen] == s[pos]) break;
      cur = tree[cur].sufflink;
    }

    if(tree[cur].next(let)){
      suff = tree[cur].next(let);
      return false;
    }

    num++;

    suff = num;
    tree[num].len = tree[cur].len + 2;
    tree[cur].next(let, num);

    if(tree[num].len == 1){
      tree[num].sufflink = 2;
      return true;
    }

    while(true){
      cur = tree[cur].sufflink;
      curLen = tree[cur].len;
      if(pos - 1 - curLen >= 0 && s[pos - 1 - curLen] == s[pos]){
	tree[num].sufflink = tree[cur].next(let);
	break;
      }
    }

    return true;
  }

  PalindromeTree(const C &s)
    : s(s), len(s.size()), tree(new node[s.size() + 3]){
    initTree();
  }

  void build(){
    for(int i = 0; i < len; i++){
      addLetter(i);
    }
  }

  static long long countSamePalindrome(C &&s, C &&t, const C &sp){
    long long ans = 0;
    const int ss = s.size();
    const C sum = s + sp + t;
    s = t = "";
    PalindromeTree tree(sum);

    vector<long long> scnt(sum.size() + 3);
    vector<long long> tcnt(sum.size() + 3);

    for(int i = 0; i < (int)sum.size(); i++){
      tree.addLetter(i);

      int pos = tree.suff;
      const node &nd = tree.tree[pos];
      if(i - nd.len + 1 < ss){
	scnt[pos]++;
      }else if(i - nd.len + 1 >= (int)(ss + sp.size())){
	tcnt[pos]++;
      }
    }

    for(int i = 0; i < 2; i++){
      vector<long long> &v = i == 0 ? scnt : tcnt;

      vector<int> ref(v.size());
      for(int j = 3; j < (int)v.size(); j++){
	if(v[j] > 0 && tree.tree[j].sufflink >= 3){
	  ref[tree.tree[j].sufflink]++;
	}
      }

      queue<int> q;
      for(int j = 3; j < (int)v.size(); j++){
	if(v[j] > 0 && ref[j] == 0) q.push(j);
      }

      while(q.size()){
	const int pos = q.front(); q.pop();
	const int suff = tree.tree[pos].sufflink;
	if(suff >= 3){
	  v[suff] += v[pos];
	  ref[suff]--;
	  if(ref[suff] == 0) q.push(suff);
	}
      }
    }

    for(int i = 3; i < (int)scnt.size(); i++){
      ans += scnt[i] * tcnt[i];
    }

    return ans;
  }
};

typedef PalindromeTree<string, 'a', 'z'> SPalindromeTree;

char buff[500000 + 10];
string getStr(){
  scanf("%s", buff);
  return buff;
}

int main(){
  string s = getStr();
  string t = getStr();

  typedef PalindromeTree<string, 'A' - 2, 'Z', 20> SPalindromeTree;
  printf("%lld\n", SPalindromeTree::countSamePalindrome(std::move(s), std::move(t), "@?"));
  return 0;
}
0