結果
| 問題 | No.263 Common Palindromes Extra |
| ユーザー |
 kei
|
| 提出日時 | 2018-09-30 23:02:48 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 163 ms / 2,000 ms |
| コード長 | 6,289 bytes |
| コンパイル時間 | 2,043 ms |
| コンパイル使用メモリ | 184,276 KB |
| 実行使用メモリ | 138,972 KB |
| 最終ジャッジ日時 | 2024-11-29 23:20:35 |
| 合計ジャッジ時間 | 3,550 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 10 ms
10,044 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | AC | 2 ms
6,820 KB |
| testcase_03 | AC | 18 ms
21,044 KB |
| testcase_04 | AC | 94 ms
92,340 KB |
| testcase_05 | AC | 104 ms
92,084 KB |
| testcase_06 | AC | 11 ms
11,476 KB |
| testcase_07 | AC | 104 ms
103,856 KB |
| testcase_08 | AC | 147 ms
103,760 KB |
| testcase_09 | AC | 112 ms
115,468 KB |
| testcase_10 | AC | 163 ms
138,972 KB |
| testcase_11 | AC | 64 ms
91,956 KB |
コンパイルメッセージ
In member function 'PalindromicTree::Node& PalindromicTree::Node::operator=(PalindromicTree::Node&&)',
inlined from 'void PalindromicTree::init(std::string&)' at main.cpp:49:22:
main.cpp:23:12: warning: '<anonymous>.PalindromicTree::Node::length' is used uninitialized [-Wuninitialized]
23 | struct Node{
| ^~~~
main.cpp: In member function 'void PalindromicTree::init(std::string&)':
main.cpp:49:22: note: '<anonymous>' declared here
49 | root1 = Node();
| ^
In member function 'PalindromicTree::Node& PalindromicTree::Node::operator=(PalindromicTree::Node&&)',
inlined from 'void PalindromicTree::init(std::string&)' at main.cpp:53:22:
main.cpp:23:12: warning: '<anonymous>.PalindromicTree::Node::length' is used uninitialized [-Wuninitialized]
23 | struct Node{
| ^~~~
main.cpp: In member function 'void PalindromicTree::init(std::string&)':
main.cpp:53:22: note: '<anonymous>' declared here
53 | root2 = Node();
| ^
ソースコード
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
/*
<url:>
問題文============================================================
=================================================================
解説=============================================================
================================================================
*/
// map使用
struct PalindromicTree{
struct Node{
int start,end; // s[start,end] = 回文となる部分文字列
int length; // 部分列長さ
map<char,int> insertEdge; // 自身のち両端に1段階拡張したノード番号へのパス
int suffixEdge; // SuffixLinkの為のノード番号
Node(){
start = end = suffixEdge = -1;
insertEdge.clear();
}
};
Node root1; // root 0 : string:imaginary string ,length = -1
Node root2; // root 1 : string:null ,length = 0
vector<Node> tree;
string s;
int ptr; // 末尾ノード番号
int currentNode; // 現在のノード番号
PalindromicTree(){}
PalindromicTree(string& str){
init(str);
}
void init(string& str){
s = str;
root1 = Node();
root1.length = -1;
root1.suffixEdge = 0;
root2 = Node();
root2.length = 0;
root2.suffixEdge = 0;
tree.clear();
tree.resize(str.length()+10);
tree[0] = root1;
tree[1] = root2;
ptr = 1;
currentNode = 0;
}
void insert(int idx){
// STEP1
// Search pattern : s[idx] X s[idx]
int now = currentNode;
while(true){
int currentLength = tree[now].length;
if((idx - currentLength >= 1)&&(s[idx] == s[idx-currentLength-1])) break;
now = tree[now].suffixEdge;
}
// もし s[idx] X s[idx] となる Xを見つけたら
// s[idx] X s[idx] がすでにノードに存在するかどうかを確認
if(tree[now].insertEdge.count(s[idx])){
// ノードが存在
currentNode = tree[now].insertEdge[s[idx]];
return;
}
// ノードが存在しないので新しいノードを作成
ptr++;
tree[now].insertEdge[s[idx]] = ptr;
Node newNode;
newNode.length = tree[now].length + 2;
newNode.end = idx;
newNode.start = idx - newNode.length + 1;
tree[ptr] = newNode;
// STEP2
//newNodeに対する suffixlinkを作成
now = tree[now].suffixEdge;
//newNodeをcurrentNodeとして設定
currentNode = ptr;
if(tree[currentNode].length == 1){
// もし回文の長さが1であれば, null文字へsuffixlinkをつなげる
tree[currentNode].suffixEdge = 1;
return;
}
while(true){
int currentLength = tree[now].length;
if((idx-currentLength >= 1) && (s[idx] == s[idx-currentLength-1])) break;
now = tree[now].suffixEdge;
}
// s[idx] Y s[idx] となる Yを発見
// suffixlinkを張る
tree[currentNode].suffixEdge = tree[now].insertEdge[s[idx]];
}
void fix(){
for(int i = 0; i < s.length();i++) insert(i);
}
void datainfo(int n){
cout << string(10,'=') << endl;
cout << "node idx : " << n << endl;
if(n == 0){
cout << "palindrome : [imaginary string]" << endl;
}else if(n==1){
cout << "palindrome : [null]" << endl;
}else{
cout << "palindrome : " << s.substr(tree[n].start,tree[n].length) << endl;
}
cout << "(l,r) : (" << tree[n].start << "," << tree[n].end << ")" << endl;
cout << "insert Edge idx :";
for(auto next:tree[n].insertEdge){
cout << next.second << " ";
}cout << endl;
cout << "suffix Edge idx :" << tree[n].suffixEdge << endl;
}
void alldatainfo(){
cout << "input string : " << s << endl;
for(int i = 0; i <= ptr;i++) datainfo(i);
}
// 出来る事.例
// 今後必要に応じて verifyできそうな問題が見つかったら適宜実装
// ユニークな回文を求める : データ見るだけ
// 特定の文字が最後になるような回文 : その文字の頂点からsuffixlinkをたどる
// 特定の位置が最後になるような回文の個数 : suffixlinkの深さを見る
// などなど
};
vector<ll> dp[2];
ll solve(){
ll res = 0;
string S,T; cin >> S >> T;
transform(S.begin(),S.end(),S.begin(),::tolower);
transform(T.begin(),T.end(),T.begin(),::tolower);
string V = S + "{|" + T;
PalindromicTree PT(V);
dp[0].resize(V.size()+5);
dp[1].resize(V.size()+5);
for(int i = 0; i < V.size();i++){
// cout << "in" << endl;
PT.insert(i);
// cout << PT.currentNode << endl;
if(i < S.length()) dp[0][PT.currentNode]++;
if(i >= S.length()+1) dp[1][PT.currentNode]++;
}
for(int i = PT.ptr; i >= 2;i--){
res += dp[0][i]*dp[1][i];
dp[0][PT.tree[i].suffixEdge] += dp[0][i];
dp[1][PT.tree[i].suffixEdge] += dp[1][i];
}
return res;
}
int main(void) {
cin.tie(0); ios_base::sync_with_stdio(false);
cout << solve() << endl;
return 0;
}