E - コメントの除去/Remove Comments Editorial by seekworser


問題文に書かれている操作を愚直に実装します。この解法は二重ループを回すため一見 \(O(N^2)\) のようにも見えますが、各文字がアルゴリズム内で参照される回数は高々 \(1\) 回であるため、全体で \(O(N)\) で動作します。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; string s;
    cin >> n >> s;
    auto find = [&] (int start_index, const string &target) -> int {
        for (int i=start_index; i<=((int)s.size() - (int)target.size()); ++i) {
            if (s.substr(i, target.size()) == target) return i;
        }
        return -1;
    };
    int pos = 0;
    string ans = "";
    while (true) {
        int i = find(pos, "/*");
        if (i == -1) break;
        int j = find(i+2, "*/");
        if (j == -1) break;
        ans += s.substr(pos, i-pos);
        pos = j+2;
    }
    ans += s.substr(pos, s.size()-pos);
    cout << ans << '\n';
}

posted:
last update: