Prefix Removals-Codeforces

投稿日：2022/03/28 更新日:2022/03/28

問題

英小文字からなる文字列 $s$ が与えられます。与えられた文字列に以下の操作を繰り返します。

$s$ のどこかに部分文字列として含まれるプレフィックスの最長の長さを $x$ とする。部分文字列はプレフィックスと交わっていてもよい。 $x = 0$ であれば終了、それ以外は $x$ 文字のプレフィックスを取り除き繰り返す。

アルゴリズムが終了時の文字列を出力。

解法

文字列 $S$ を $s_1s_2...s_n$ とします。
操作が終了する条件は $s_1$ が $s_2...s_n$ に含まれていない時であることが分かります。そのような条件になるまで前の文字列を消します。
問題文には「最長のプレフィックス」と書いていますが、前から1文字づつ判定して消しても結果として同じであることが分かります。

$s_i$ が $s_{i+1}...s_n$ に含まれるかどうかは、mapを用いて事前にカウントして判定します。

実装

#include <bits/stdc++.h>
using namespace std;

void solve(){
    string s;
    cin >> s;

    int n = s.length();
    map<char, int> mp;
    for(int i = 0;i < n; ++i){
        mp[s[i]]++;
    }

    int ansi = 0;
    for(int i = 0;i < n; ++i){
        mp[s[i]]--;
        if(mp[s[i]] == 0){
            ansi = i;
            break;
        }
    }

    for(int i = ansi; i < n; ++i){
        cout << s[i];
    }
    cout << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}