C++で長さMのすべての異なる循環文字列を辞書順に出力する方法

この問題では、文字列と整数Mが与えられます。求められているのは、その文字列から生成できる長さMのすべての異なる循環文字列を、辞書順（アルファベット順）で出力することです。

問題の例

具体例を使って問題を理解しましょう。

入力: str = "ssssn", M = 3
出力: nss sns ssn sss

説明 − 長さ3の循環文字列として生成できるのは「sss」「sss」「ssn」「sns」「nss」の5つです。ここから重複を除き、辞書順に並べ替えると「sss ssn sns nss」が答えとなります。

解決策のアプローチ

この問題を解くには、以下の手順に従います。

まず、元の文字列を2回連結した文字列（s + s）を作成します。これにより、末尾に折り返す循環的な部分文字列も簡単に取り出せるようになります。

次に、文字列の各位置から長さMの部分文字列をすべて生成します。生成した部分文字列は、set（集合）に格納します。C++のsetは重複する要素を自動的に排除し、要素を常に辞書順に保持するため、この問題に最適なデータ構造です。

最後に、setの先頭から順にすべての要素を出力すれば、辞書順に並べ替えられた重複のない循環文字列が得られます。

計算量

このアルゴリズムの計算量は、文字列の長さNと部分文字列の長さMに依存し、時間計算量は O(N×M) となります。

実装例

以下のコードは、上記の解決策の実装例です。

#include <bits/stdc++.h>
using namespace std;
void printCircularString(string s, int l, int m) {
    set<string> circularString;
    s = s + s;
    for (int i = 0; i < l; i++) {
        circularString.insert(s.substr(i, m));
    }
    while (!circularString.empty()) {
        cout<<*circularString.begin()<<"\t";
        circularString.erase(circularString.begin());
    }
}
int main() {
    string str = "ssssn";
    int N = str.length();
    int M = 3;
    cout<<"All circular strings of length "<<M<<" from the string '"<<str<<"' are:\n";
    printCircularString(str, N, M);
    return 0;
}

出力結果

All circular strings of length 3 from the string 'ssssn' are −
nss sns ssn sss

まとめ

文字列を2倍にしてから長さMの部分文字列をすべて生成し、setに格納するだけで、重複排除と辞書順ソートが自動的に行われます。シンプルでありながら効率的な手法なので、同様の文字列処理の問題にも応用できます。