c++ - 查找字符串中字典序最大的旋转

Question

我需要从给定的输入字符串中找出字典序最大的字符串。 所以如果输入是

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。
如何跟踪最大字符之前的每个元素以获得正确的输出？

Answer 1

为了在平均情况下获得良好的性能(实际上是 O(N))，但在最坏的情况下仍然是 O^2(并且始终正确)，您可以跟踪可能性，并在进行时不断消除它们。基本上是这样的。

struct PermSum
{
  int sum;
  int perm;
}

LinkedList<PermSum> L;

for(int i = 0; i != input.size(); ++i) L.append(PermSum{0,i});

int depth = 0;
int max = 0;
const int length = input.size()
while(L.size() > 1 && depth < length)
{
  for(l in L)
  {
    l.sum += input[(l.perm + depth) % length]
    if (l.sum > max) max = l.sum
  }

  for(l in L)
  {
    if (l.sum < max) L.delete(l)
  }
  depth ++;
}

if (L.size() == 1)
  return L.front().perm
else
  return -1

我在 C++ 代码的某些部分有点懒惰，但我相信您可以找出 for l in L。关键行是第一个 for 循环。这个想法是它在第 l.perm-th 排列的第 depth-th 个字母处添加字典序值。通过这种方式，它会更新所有可能性，同时跟踪最佳可能性的级别。然后，您进行第二遍以删除任何达不到最佳效果的可能性。值得注意的是，我编写代码的方式可能使用与循环排列的标准约定相反的方式。也就是说，我程序中的 perm 字段表示循环移动左移的点数，而通常正数是循环右移。您可以在某处使用减号来解决此问题。

至于运行时间分析，基本和Quickselect是同一个论点。每个 while 循环迭代花费的时间与 L 的长度成正比。第一次迭代，L 将始终具有长度 = N(其中 N 是字符串的长度，与代码中的变量长度相同)。下一轮，我们通常只期望 1/26 的数据通过，下一轮又是 1/26...所以我们有 N(1 + 1/26 + 2/26^2...)是 O(N)。