2

指定された入力文字列から辞書編集的に最大の文字列を見つける必要があります。したがって、入力が

enjoy

o/p は

yenjo

私が試したコードは....

int n;
cout<<"Enter the number of strings";
cin>>n;
int len[n];
char str[n][1000];
for(int i=0;i<n;i++)
{
    cin>>str[i];
    len[i]=strlen(str[i]);
}
int num,pos[n];
for(int i=0;i<n;i++)
{
    pos[i]=0;
    num=int(str[i][0]);
    for(int j=1;j<len[i];j++)
    {
       if(int(str[i][j])>num)
        {
           num=int(str[i][j]);
           pos[i]=j;
       }   
    }    
}
int i,j,k;
char temp[1];
for(i=0;i<n;i++)
{
    for(j=0;j<pos[i];j++)
        {
        temp[0]=str[i][0];
        for(k=0;k<len[i];k++)
         {
            str[i][k]=str[i][k+1];
        }
        strcat(str[i],temp);
        str[i][len[i]]='\0';
    }
    cout<<str[i]<<"\n";
}
return 0;
}

しかし、このコードは最大の数字のみを確認し、その隣にある数字は確認しないため、i/p では失敗します。

blowhowler

o/p は である必要がありますwlerblowhoが、o/p を として取得しwhowlerbloます。
正しい出力を得るために、最大の文字の前にある各要素を追跡するにはどうすればよいですか?

4

7 に答える 7

1 
//Here the index with greater value is selected,
//if the same char occurs again the next characters
// of prev and curr characters is checked:-Prev=maxIndex,curr=i    
#include<bits/stdc++.h>
using namespace std;
int getIndex(char *str){
int max=INT_MIN,maxIndex;
int n=strlen(str);
int j,p;
for(int i=0;i<n;i++)
{
    if(str[i]>max)
    {
        max=str[i];
        maxIndex=i;
    }
    else if(str[i]==max)
    {
        j=maxIndex+1;
        p=(i+1)%n;
        while(j<n && p<n && str[j]==str[p]){
         j++;
         p=(p+1)%n;
        }
        maxIndex=str[p]>str[j]?i:maxIndex;
    }
}
return maxIndex;
}
int main(void)
{
char str[4000008];
scanf("%s",str);
int i=getIndex(str);
for(int j=i;j<strlen(str);j++)
cout<<str[j];
for(int j=0;j<i;j++)
cout<<str[j];



 }
于 2016-08-09T14:36:24.403 に答える
1

The problem can be solved in O(n log n) time by appending the string to itself first and build the suffix array out of it. Find the corresponding entry and there your wanted result. Implementation left as an exercise.

于 2014-09-18T08:50:13.227 に答える
1

1. 回転を生成する 2. すべての回転を map<> に入れる 3. マップの最後の要素を見つける。C++ での実装は次のとおりです。

#include <iostream>
#include <cstring>
#include <map>
using namespace std;

int main() {
    // your code goes here
    string str;int len,i=0,j=0,k=0;char temp;
    cin>>str;
    len = str.length();
    map<string,int>m;
    while(i<len)
    {
        temp = str[0];
        while(j<len-1)
        {
            str[j] = str[j+1];
            j++;
        }
        str[j] = temp;
        m[str] = k;
        k++;
        i++;j=0;
    }
    str = m.rbegin()->first;
    cout<<str;
    return 0;
}
于 2014-09-18T08:37:08.140 に答える
0

このチャレンジはアクティブなコンテストで使用されます。9 月 18 日午後 9 時 (IST) まで回答を求めません。コードが表示されるため、ユーザーが今後コンテストに参加することを禁止する必要がある場合があります。

于 2014-09-18T12:38:48.327 に答える
0

これはあまりにも魅力的だったので、自分の努力を投稿したほうがよいでしょう。それが効率をどのように評価するかはわかりません。私がテストした限りではうまくいくようです：

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

std::string max_rot(const std::string& s)
{
    std::string tmp;
    std::string max;

    std::string::const_iterator m = std::max_element(s.begin(), s.end());
    if(m != s.end())
        for(char c = *m; (m = std::find(m, s.end(), c)) != s.end(); ++m)
            if(max < tmp.assign(m, s.end()).append(s.begin(), m))
                max = tmp;

    return max;
}


int main()
{
    size_t times = 0;
    std::string text;

    do { std::cout << "\nHow many words? : "; }
    while(std::getline(std::cin, text) && !(std::istringstream(text) >> times));

    std::vector<std::string> words;
    while(times-- && (std::cin >> text))
        words.push_back(text);

    for(const auto& s: words)
        std::cout << max_rot(s) << '\n';

}

説明通り。文字列内の最大の文字値を見つけ、文字列を回転させてその文字を最初に作成します。次に、最大の試行を追跡する文字列の残りの部分で、重複する最大の文字を探します。最適化の余地があるかもしれません。

于 2014-09-18T03:22:54.913 に答える
0

修正されたアルゴリズムは、次のようになります。

  1. 現在の最適な回転を ID に設定します (回転された文字列の開始は現在のインデックス 0 です)。
  2. 可能な回転ごとに (他のすべての開始インデックス):
    1. 以下のようなもので current-best-rotation と比較してくださいwrapcmp。
    2. より良い候補があれば、current-best-rotation を設定します。

時間の複雑さ: O(n*n)
空間の複雑さ: インプレース

// Function to do ordinal-comparison on two rotations of a buffer
// buffer: The buffer containing the string
// n: The buffers size (string-length)
// a: Index where the first buffer starts pre-rotation
// b: Index where the second buffer starts pre-rotation
int wrapcmp(const void* buffer, size_t n, size_t a, size_t b) {
    auto x = (const unsigned char*)buffer;
    auto m = n - std::max(a, b);
    int ret = memcmp(x+a, x+b, m);
    if(ret) return ret;
    auto left = n - m;
    a = (a + m) % n;
    b = (b + m) % n;
    m = left - std::max(a, b);
    ret = memcmp(x+a, x+b, m);
    if(ret) return ret;
    a = (a + m) % n;
    b = (b + m) % n;
    return memcmp(x+a, x+b, left - m);
}

coliru で使用: http://coliru.stacked-crooked.com/a/4b138a6394483447
読者の演習として残されている一般的なアルゴリズムにそれを入れます。

于 2014-09-17T23:00:04.353 に答える