結果

問題 No.2172 SEARCH in the Text Editor
コンテスト
ユーザー Nachia
提出日時 2022-12-24 02:02:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,342 bytes
コンパイル時間 1,882 ms
コンパイル使用メモリ 107,156 KB
最終ジャッジ日時 2025-02-09 19:53:57
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <atcoder/string>
#include <atcoder/modint>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
using Modint = atcoder::static_modint<998244353>;

const int SZ = 50;
const int SZZ = SZ * (SZ+1) / 2;

int Z(const string& preof, const string& sufof){
    int x = min(preof.size(), sufof.size());
    auto z = atcoder::z_algorithm(preof.substr(0, x) + sufof.substr(sufof.size() - x));
    for(int i=x; i>=1; i--) if(z[z.size()-i] >= i) return i;
    return 0;
}

string T;
int t;
int T6L[SZ+1]={}, T6R[SZ+1]={};
int T5[SZ+1][SZ+1]={};
string TPRE[SZ+1];
string TSUF[SZ+1];
vector<string> substrs;
int T4[SZZ][SZZ]={};
int T3L[SZZ]={}, T3R[SZZ]={};
int T2L[SZZ][SZ]={}, T2R[SZZ][SZ]={};
int T1[SZ][SZ]={};
void precalc(){
    t = T.size();
    rep(i,t+1) TPRE[i] = T.substr(0, i);
    rep(i,t+1) TSUF[i] = T.substr(t-i);
    rep(i,t+1) T6L[i] = i ? Z(TSUF[i].substr(0,i-1), T) : 0;
    rep(i,t+1) T6R[i] = i ? Z(T, TPRE[i].substr(1)) : 0;
    auto sa = atcoder::suffix_array(T);
    auto lcp = atcoder::lcp_array(T, sa);
    rep(i,t+1) rep(j,t+1) T5[i][j] = -1;
    rep(i,t){
        int k = i ? lcp[i-1] : 0;
        for(int j=1; j<=t-sa[i] && j<t; j++){
            if(j <= k){ T5[sa[i]][j] = T5[sa[i-1]][j]; continue; }
            T5[sa[i]][j] = substrs.size();
            substrs.push_back(T.substr(sa[i],j));
        }
    }
    int nn = substrs.size();
    rep(i,nn) rep(j,nn) T4[i][j] = -1;
    rep(k,t+1) rep(j,k) rep(i,j) T4[T5[i][j-i]][T5[j][k-j]] = T5[i][k-i];
    rep(j,nn) T3L[j] = Z(substrs[j], T);
    rep(j,nn) T3R[j] = Z(T, substrs[j]);
    rep(j,nn) rep(x,t) T2L[j][x] = Z(substrs[j] + TSUF[x], TSUF[t-1]);
    rep(j,nn) rep(x,t) T2R[j][x] = Z(TPRE[t-1], TPRE[x] + substrs[j]);
    for(int i=1; i<t; i++) T1[i][t-i] = 1;
    for(int d=t+1; d<2*t; d++) for(int i=d-t+1; i<t; i++) T1[i][d-i] = T1[T6R[i]][d-i] + T1[i][T6L[d-i]] - T1[T6R[i]][T6L[d-i]];
}

struct Node{ int l; int r; Modint c; };
Node createNode(const string& s){
    if(s.size() < T.size()){
        auto x = lower_bound(substrs.begin(), substrs.end(), s);
        if(x != substrs.end() && *x == s) return Node{ (int)(x-substrs.begin()), -1, Modint() };
        return Node{ Z(s,TSUF[t-1]), Z(TPRE[t-1],s), Modint() };
    }
    int cnt = 0;
    auto z = atcoder::z_algorithm(T + s);
    rep(i,s.size()) if(z[t+i]>=t) cnt++;
    return Node{ Z(s,TSUF[t-1]), Z(TPRE[t-1],s), Modint::raw(cnt) };
}
Node mergeNode(Node l, Node r){
    if(l.r >= 0){
        if(r.r >= 0) return { l.l, r.r, l.c + r.c + Modint::raw(T1[l.r][r.l]) };
        return { l.l, T2R[r.l][l.r], l.c + Modint::raw(T1[l.r][T3L[r.l]]) };
    }
    if(r.r < 0){
        int nx = T4[l.l][r.l];
        if(nx >= 0) return { nx, -1, Modint() };
        int lr = T3R[l.r], rl = T3L[r.l];
        return { T2L[l.l][rl], T2R[r.l][lr], Modint::raw(T1[lr][rl]) };
    }
    return { T2L[l.l][r.l], r.r, r.c + Modint::raw(T1[T3R[l.l]][r.l]) };
}

int main() {
    int N; cin >> N;
    cin >> T;
    precalc();
    vector<Node> X(N);
    rep(i,N){
        string s; cin >> s;
        if(s == "~"){
            int j,k; cin >> j >> k;
            X[i] = mergeNode(X[j-1], X[k-1]);
        }
        else{
            X[i] = createNode(s);
        }
    }
    cout << X[N-1].c.val() << '\n';
    return 0;
}
0