結果

問題 No.1192 半部分列
ユーザー square1001
提出日時 2020-08-22 14:10:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 1,121 bytes
コンパイル時間 687 ms
コンパイル使用メモリ 77,828 KB
実行使用メモリ 30,592 KB
最終ジャッジ日時 2024-10-15 08:26:35
合計ジャッジ時間 1,925 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
vector<vector<int> > calc_next(string S) {
    int N = S.size();
    vector<vector<int> > dp(N + 1, vector<int>(26, inf));
    for (int i = N - 1; i >= 0; --i) {
        dp[i] = dp[i + 1];
        dp[i][S[i] - 'a'] = i;
    }
    return dp;
}
int main() {
    string S, T;
    cin >> S >> T;
    int LS = S.size(), LT = T.size();
    vector<int> dp(LS + 1); dp[LS] = LT;
    int ptr = LT;
    for (int i = LS - 1; i >= 0; --i) {
        while (ptr != -1) {
            --ptr;
            if (ptr != -1 && S[i] == T[ptr]) break;
        }
        dp[i] = ptr;
    }
    vector<vector<int> > ns = calc_next(S);
    vector<vector<int> > nt = calc_next(T);
    string ans;
    int posa = 0, posb = 0;
    while (true) {
        bool found = false;
        for (int i = 0; i < 26; ++i) {
            if (ns[posa][i] != inf && dp[ns[posa][i] + 1] <= nt[posb][i]) {
                posa = ns[posa][i] + 1;
                posb = nt[posb][i] + 1;
                ans += char('a' + i);
                found = true;
                break;
            }
        }
        if (posb >= inf) {
            break;
        }
        if (!found) break;
    }
    if (ans.empty()) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0