結果
| 問題 | No.263 Common Palindromes Extra |
| ユーザー |
 kei
|
| 提出日時 | 2018-09-30 22:40:22 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,393 bytes |
| コンパイル時間 | 1,861 ms |
| コンパイル使用メモリ | 181,660 KB |
| 実行使用メモリ | 194,324 KB |
| 最終ジャッジ日時 | 2024-11-29 23:15:14 |
| 合計ジャッジ時間 | 3,359 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 10 ms
7,296 KB |
| testcase_04 | AC | 37 ms
22,672 KB |
| testcase_05 | AC | 32 ms
22,160 KB |
| testcase_06 | AC | 5 ms
5,248 KB |
| testcase_07 | AC | 92 ms
65,140 KB |
| testcase_08 | AC | 90 ms
64,908 KB |
| testcase_09 | AC | 137 ms
107,636 KB |
| testcase_10 | MLE | - |
| testcase_11 | AC | 30 ms
21,640 KB |
コンパイルメッセージ
In member function 'PalindromicTree::Node& PalindromicTree::Node::operator=(PalindromicTree::Node&&)',
inlined from 'void PalindromicTree::init(std::string&)' at main.cpp:50:22,
inlined from 'PalindromicTree::PalindromicTree(std::string&)' at main.cpp:45:13,
inlined from 'll solve()' at main.cpp:153:25:
main.cpp:25:12: warning: '<anonymous>.PalindromicTree::Node::length' may be used uninitialized [-Wmaybe-uninitialized]
25 | struct Node{
| ^~~~
main.cpp: In function 'll solve()':
main.cpp:50:22: note: '<anonymous>' declared here
50 | root1 = Node();
| ^
In member function 'PalindromicTree::Node& PalindromicTree::Node::operator=(PalindromicTree::Node&&)',
inlined from 'void PalindromicTree::init(std::string&)' at main.cpp:54:22,
inlined from 'PalindromicTree::PalindromicTree(std::string&)' at main.cpp:45:13,
inlined from 'll solve()' at main.cpp:153:25:
main.cpp:25:12: warning: '<anonymous>.PalindromicTree::Node::length' may be used uninitialized [-Wmaybe-uninitialized]
25 | struct Node{
| ^~~~
main.cpp: In function 'll solve()':
main.cpp:54:22: note: '<anonymous>' declared here
54 | 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:https://yukicoder.me/problems/no/263>
問題文============================================================
=================================================================
解説=============================================================
================================================================
*/
// PalindromicTreeを用いる時の文字に注意(大文字、小文字)
// MLEする場合はinsertEdgeをmapにすると改善の見込みあり
struct PalindromicTree{
struct Node{
int start,end; // s[start,end] = 回文となる部分文字列
int length; // 部分列長さ
vector<int> insertEdge; // 自身のち両端に1段階拡張したノード番号へのパス
int suffixEdge; // SuffixLinkの為のノード番号
Node(){
start = end = suffixEdge = -1;
insertEdge = vector<int>(28,-1);
}
};
Node root1; // root 0 : string:imaginary string ,length = -1
Node root2; // root 1 : string:null ,length = 0
vector<Node> tree;
string s;
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.push_back(root1);
tree.push_back(root2);
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[s[idx]-'a'] != -1){
// ノードが存在
currentNode = tree[now].insertEdge[s[idx]-'a'];
return;
}
// ノードが存在しないので新しいノードを作成
int newNodenum = (int)tree.size();
tree[now].insertEdge[s[idx]-'a'] = newNodenum;
Node newNode;
newNode.length = tree[now].length + 2;
newNode.end = idx;
newNode.start = idx - newNode.length + 1;
tree.push_back(newNode);
// STEP2
//newNodeに対する suffixlinkを作成
now = tree[now].suffixEdge;
//newNodeをcurrentNodeとして設定
currentNode = newNodenum;
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]-'a'];
}
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){
if(next == -1) continue;
cout << next << " ";
}cout << endl;
cout << "suffix Edge idx :" << tree[n].suffixEdge << endl;
}
void alldatainfo(){
cout << "input string : " << s << endl;
for(int i = 0; i < tree.size();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++){
PT.insert(i);
if(i < S.length()) dp[0][PT.currentNode]++;
if(i >= S.length()+1) dp[1][PT.currentNode]++;
}
for(int i = (int)PT.tree.size(); 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;
}