AtCoder Beginner Contest 223 B - String Shifting
問題の要約
空でない文字列に対し,先頭の文字を末尾に移動する操作を左シフト,末尾の文字を先頭に移動する操作を右シフトと呼ぶ。
英小文字からなる空でない文字列Sが与えられる。
Sに対し左シフトと右シフトをそれぞれ好きな回数(0回でもよい)行って得られる文字列のうち,辞書順で最小のものと最大のものを求めよ。
制約
Sは英小文字からなる。
Sの長さは1以上1000以下である。
考え方
1,二つの操作があるが,左シフトだけ行った操作でできる文字列の集合と右シフトだけ行った操作でできる文字列の集合は同じ。
途中に別の操作を入れると前の文字列に戻るだけなので,考える必要はない。
よって左シフトの操作だけを考える。
2,先頭の文字を末尾に移動するという操作は面倒くさい。
最初から左シフトを文字列の回数分だけ行うことを前提としてSを二つ結合したものを文字列SSとする。
これで単純なfor文で左シフトをi回(0<=i<=|S|-1)行ったときの文字列を抜き出すことができる。
3,あとはこれをvectorに挿入して,sortして,最初の文字列が辞書順最小で,最後の文字列が辞書順最大の文字列である。
実際のプログラム
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main(){
string S;
cin >> S;
string SS = S+S;
vector<string> Ss;
for(int i = 0; i < S.size(); i++){
Ss.push_back(SS.substr(i, S.size()));
}
sort(Ss.begin(), Ss.end());
cout << Ss[0] << endl;
cout << Ss[S.size()-1] << endl;
return 0;
}