結果

問題 No.263 Common Palindromes Extra
ユーザー y_mazuny_mazun
提出日時 2015-08-31 21:21:53
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 188 ms / 2,000 ms
コード長 3,074 bytes
コンパイル時間 2,051 ms
コンパイル使用メモリ 72,924 KB
実行使用メモリ 144,320 KB
最終ジャッジ日時 2023-08-20 00:33:46
合計ジャッジ時間 3,034 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
13,912 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 20 ms
31,152 KB
testcase_04 AC 133 ms
143,180 KB
testcase_05 AC 111 ms
143,216 KB
testcase_06 AC 10 ms
16,456 KB
testcase_07 AC 151 ms
144,312 KB
testcase_08 AC 146 ms
144,320 KB
testcase_09 AC 188 ms
143,320 KB
testcase_10 AC 188 ms
143,260 KB
testcase_11 AC 115 ms
143,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;

template<typename C, typename C::value_type low, typename C::value_type high>
class PalindromeTree{
  const static int m = high - low + 1;
  typedef typename C::value_type T;

  struct node{
    int next[m];
    int len;
    int sufflink;
  };

  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:
  vector<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(s.size() + 3){
    initTree();
  }

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

  static long long countSamePalindrome(const C &s, const C &t, const C &sp){
    long long ans = 0;
    const C sum = s + sp + 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 < (int)s.size()){
	scnt[pos]++;
      }else if(i - nd.len + 1 >= (int)(s.size() + 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(){
  const string s = getStr();
  const string t = getStr();

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