結果
問題 | No.1192 半部分列 |
ユーザー |
![]() |
提出日時 | 2020-07-30 10:03:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,846 bytes |
コンパイル時間 | 802 ms |
コンパイル使用メモリ | 74,000 KB |
実行使用メモリ | 30,720 KB |
最終ジャッジ日時 | 2024-07-06 18:36:39 |
合計ジャッジ時間 | 2,629 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <iostream> #include <string> #include <vector> using namespace std; const int alphabet_size = 26; int main() { string s, t; cin >> s >> t; int ss = s.size(), ts = t.size(); vector<vector<int>> s_next(ss + 1, vector<int>(alphabet_size, ss)); for (int i = ss - 1; i >= 0; --i) { for (int j = 0; j < alphabet_size; ++j) { s_next[i][j] = s_next[i + 1][j]; } s_next[i][s[i] - 'a'] = i; } vector<vector<int>> t_next(ts + 1, vector<int>(alphabet_size, ts)); for (int i = ts - 1; i >= 0; --i) { for (int j = 0; j < alphabet_size; ++j) { t_next[i][j] = t_next[i + 1][j]; } t_next[i][t[i] - 'a'] = i; } vector<int> back_substr(ss + 1, ts); int k = ts; for (int i = ss - 1; i >= 0; --i) { while (k > 0) { --k; if (s[i] == t[k]) { back_substr[i] = k; break; } } if (back_substr[i] == ts) back_substr[i] = -1; } if (back_substr[0] != -1) { cout << -1 << endl; return 0; } string ans; int s_cnt = 0, t_cnt = 0; bool ended = false; while (!ended) { for (int i = 0; i < alphabet_size; ++i) { if (s_next[s_cnt][i] == ss) { continue; } else if (t_next[t_cnt][i] == ts) { ans.push_back('a' + i); ended = true; break; } else { if (back_substr[s_next[s_cnt][i] + 1] < t_next[t_cnt][i] + 1) { s_cnt = s_next[s_cnt][i] + 1; t_cnt = t_next[t_cnt][i] + 1; ans.push_back('a' + i); break; } } } } cout << ans << endl; return 0; }