【1-2】辞書順の問題

1808 ワード

´問題記述:データ暗号化やデータ圧縮では、特殊な文字列を符号化する必要があることが多い.与えられたアルファベットAは26個の小文字英字からなるA={a,b,...,z}である.このアルファベットによって生成される昇順文字列とは、文字列中のアルファベットが左から右に現れる順序でアルファベットがアルファベットに現れる順序と同じであり、各文字が最大1回現れることを意味する.例えば、a,b,ab,bc,xyzなどの文字列はいずれも昇順文字列である.現在、アルファベットAに対して生成されたすべての長さが6を超えない昇順文字列は、辞書順に並べられ、以下のように符号化されている.1 2...26 27...a b...z ab ac...任意の長さが6を超えない昇順文字列について、上記辞書での符号化を迅速に算出する.´プログラミングタスク:6を超えない長さの昇順文字列について、上記の辞書での符号化をプログラミングして計算します.´データ入力:入力データはファイル名input.txtのテキストファイルが提供されます.ファイルの最初の行は正の整数kであり、次にk行が共有されることを示す.次のk行では、各行に文字列が与えられます.´結果出力:プログラム実行終了時に、計算結果をファイルoutputに出力.txtで.ファイルにはk行が共有され、各行は1文字列の符号化に対応する.入力ファイル例出力ファイル例input.txt output.txt 2 a b 1 2
【問題解】
最初は文字列が空です.次に、i-1の文字列から辞書順にsを取り出し、sの後ろに適切な文字を付けてiの文字列を生成すればよい.最後にmapで各文字列にラベルを付ける
【コード】
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

vector  v[7];
unordered_map dic;

int main(){
    v[0].push_back("");
    for (int i = 1;i <= 6;i++){
        int len = v[i-1].size();
        for (int j = 0;j < len;j++){
            string temp = v[i-1][j];
            int len2 = temp.size();
            char key = 'a';
            if (temp!=""){
                key = temp[len2-1]+1;
            }
            for (char q = key;q<='z';q++){
                v[i].push_back(""+temp+q);
            }
        }
    }
    int cur = 0;
    for (int i = 1;i <= 6;i++){
        int len = v[i].size();
        for (int j = 0;j < len;j++){
            dic[v[i][j]] = ++cur;
        }
    }
    int k;
    cin >> k;
    while (k--){
        string s;
        cin >> s;
        cout<