結果
問題 | No.2231 Surprising Flash! |
ユーザー |
👑 ![]() |
提出日時 | 2023-02-14 03:24:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,083 bytes |
コンパイル時間 | 3,841 ms |
コンパイル使用メモリ | 147,436 KB |
最終ジャッジ日時 | 2025-02-10 15:13:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 WA * 3 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <atcoder/string>#include <atcoder/convolution>#include <atcoder/segtree>using namespace std;using namespace atcoder;typedef long long ll;template<typename T> void debug(vector<T> &v){for (ll i = 0; i < v.size(); i++){cerr << v[i] << " ";}cerr << endl;}ll ctol(char c){ll ret;if (c == '?') ret = 0;else{ret = (ll)(c - 'a' + 1);}return ret;}vector<ll> wild_card_matching(string &S, string &T){ll len_S = S.size();ll len_T = T.size();vector<vector<ll>> pow_S(4, vector<ll>(len_S));vector<vector<ll>> pow_T(4, vector<ll>(len_T));for (ll i = 0; i < len_S; i++){pow_S[1][i] = ctol(S[i]);for (ll j = 1; j < 3; j++){pow_S[j + 1][i] = pow_S[j][i] * pow_S[1][i];}}for (ll i = 0; i < len_T; i++){pow_T[1][i] = ctol(T[i]);for (ll j = 1; j < 3; j++){pow_T[j + 1][i] = pow_T[j][i] * pow_T[1][i];}}for (ll i = 0; i < 4; i++){reverse(pow_T[i].begin(), pow_T[i].end());}vector<ll> vec_conv1 = convolution_ll(pow_S[3], pow_T[1]);vector<ll> vec_conv2 = convolution_ll(pow_S[2], pow_T[2]);vector<ll> vec_conv3 = convolution_ll(pow_S[1], pow_T[3]);vector<ll> ret(0);for (ll i = 0; i < len_S - len_T + 1; i++){if (vec_conv1[len_T - 1 + i] - 2 * vec_conv2[len_T - 1 + i] + vec_conv3[len_T - 1 + i] == 0){ret.push_back(i);}}return ret;}ll op(ll a, ll b){return min(a, b);}ll e(){return 1e9;}int main(){ll T;cin >> T;while(T--){ll N, M;cin >> N >> M;string S1;cin >> S1;string S2;cin >> S2;vector<ll> wcm = wild_card_matching(S1, S2);if (wcm.size() == 0){cout << -1 << endl;continue;}//debug(wcm);string S3 = "";for (ll i = 0; i < N; i++){if (S1[i] == '?') S3.push_back('a');else S3.push_back(S1[i]);}//S3 + S2 の LCP を求めるvector<int> sa = suffix_array(S3 + S2);vector<int> lcp = lcp_array(S3 + S2, sa);vector<int> rev_sa(N + M);for (int i = 0; i < N + M; i++){rev_sa[sa[i]] = i;}segtree<ll, op, e> seg(N + M);for (ll i = 0; i < N + M; i++){seg.set(i, lcp[i]);}ll idx = 0;for (ll i = 1; i < wcm.size(); i++){ll left, right;ll diffs = wcm[i] - wcm[idx];if (diffs >= M){idx = i;continue;}left = min(rev_sa[wcm[idx]], rev_sa[N]);right = max(rev_sa[wcm[idx]], rev_sa[N]);ll lcp1 = seg.prod(left, right);if (lcp1 < diffs){if (S3[wcm[i] + lcp1] < S2[lcp1]){idx = i;continue;}else{continue;}}left = min(rev_sa[N], rev_sa[N + diffs]);right = max(rev_sa[N], rev_sa[N + diffs]);ll lcp2 = seg.prod(left, right);if (lcp2 < M - diffs){if (S2[lcp2] < S2[diffs + lcp2]){idx = i;continue;}else{continue;}}left = min(rev_sa[wcm[idx] + M], rev_sa[N + M - diffs]);right = max(rev_sa[wcm[idx] + M], rev_sa[N + M - diffs]);ll lcp3 = seg.prod(left, right);if (lcp3 < diffs){if (S2[M - diffs + lcp3] < S3[wcm[idx] + M + lcp3]){idx = i;continue;}else{continue;}}}cout << S3.substr(0, wcm[idx]) << S2 << S3.substr(wcm[idx] + M, N - wcm[idx]) << endl;}}