9

私はspojでこの問題を解決しようとしています

すべての回転の中で辞書編集的に最小になる特定の文字列の回転数を見つける必要があります。

例えば：

オリジナル：ama

最初のローテーション:maa

2 番目のローテーション:aamこれは辞書編集的に最小のローテーションなので、答えは 2 です。

これが私のコードです：

string s,tmp;
    char ss[100002];
    scanf("%s",ss);
    s=ss;
    tmp=s;
    int i,len=s.size(),ans=0,t=0;
    for(i=0;i<len;i++)
    {
        string x=s.substr(i,len-i)+s.substr(0,i);
        if(x<tmp)
        {
            tmp=x;
            t=ans;
        }
        ans++;
    }

    cout<<t<<endl;

このソリューションで「時間制限を超えました」というメッセージが表示されます。どのような最適化を行うことができるかわかりません。ソリューションの速度を上げるにはどうすればよいですか?

4

2 に答える 2

2

変更されたサフィックス配列を使用できます。単語の終わりで止めてはならないので、変更されたという意味です。

私が解決した同様の問題のコードは次のとおりです（SAはサフィックス配列です）：

//719
//Glass Beads
//Misc;String Matching;Suffix Array;Circular
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <cmath>
#define MAX 10050
using namespace std;

int RA[MAX], tempRA[MAX];
int SA[MAX], tempSA[MAX];
int C[MAX];                

void suffix_sort(int n, int k) {
    memset(C, 0, sizeof C);        

    for (int i = 0; i < n; i++)        
        C[RA[(i + k)%n]]++;

    int sum = 0;
    for (int i = 0; i < max(256, n); i++) {                     
        int t = C[i]; 
        C[i] = sum; 
        sum += t;
    }

    for (int i = 0; i < n; i++)        
        tempSA[C[RA[(SA[i] + k)%n]]++] = SA[i];

    memcpy(SA, tempSA, n*sizeof(int));
}

void suffix_array(string &s) {             
    int n = s.size();

    for (int i = 0; i < n; i++) 
        RA[i] = s[i];              

    for (int i = 0; i < n; i++) 
        SA[i] = i;

    for (int k = 1; k < n; k *= 2) {     
        suffix_sort(n, k);
        suffix_sort(n, 0);

        int r = tempRA[SA[0]] = 0;
        for (int i = 1; i < n; i++) {
            int s1 = SA[i], s2 = SA[i-1];
            bool equal = true;
            equal &= RA[s1] == RA[s2];
            equal &= RA[(s1+k)%n] == RA[(s2+k)%n];

            tempRA[SA[i]] = equal ? r : ++r;     
        }

        memcpy(RA, tempRA, n*sizeof(int));
    } 
}

int main() {
    int tt; cin >> tt;
    while(tt--) {
        string s; cin >> s;
        suffix_array(s);
        cout << SA[0]+1 << endl;
   }
}

この実装は、主にこの本から引用しました。O(n log²n) バージョンを書くのは簡単ですが、あなたの場合 (n=10^5) には十分に効率的ではないかもしれません。このバージョンは O(n log n) であり、最も効率的なアルゴリズムではありません。ウィキペディアの記事にはいくつかの O(n) アルゴリズムがリストされていますが、それらのほとんどは複雑すぎてプログラミング コンテスト中に書くことができません。この O(n log n) は通常、ほとんどの問題に対して十分です。

接尾辞配列の概念を説明するいくつかのスライドを見つけることができます (私が言及した本の著者から)ここ.

于 2013-02-21T14:54:09.660 に答える
1

これが非常に遅いことはわかっていますが、このアルゴリズムのさらに高速なバリアントを検索しているときに、Google からこれに出くわしました。適切な実装が github にあることがわかりました: https://gist.github.com/MaskRay/8803371

リンドン因数分解を使用します。つまり、文字列を辞書順で減少する lyndon 単語に繰り返し分割します。Lyndon ワードは、それ自体の最小回転 (の 1 つ) である文字列です。これを循環的に行うと、文字列の lms が最後に見つかったリンドン ワードとして生成されます。

int lyndon_word(const char *a, int n)
{
  int i = 0, j = 1, k;
  while (j < n) {
    // Invariant: i < j and indices in [0,j) \ i cannot be the first optimum
    for (k = 0; k < n && a[(i+k)%n] == a[(j+k)%n]; k++);
    if (a[(i+k)%n] <= a[(j+k)%n]) {
      // if k < n
      //   foreach p in [j,j+k], s_p > s_{p-(j-i)}
      //   => [j,j+k] are all suboptimal
      //   => indices in [0,j+k+1) \ i are suboptimal
      // else
      //   None of [j,j+k] is the first optimum
      j += k+1;
    } else {
      // foreach p in [i,i+k], s_p > s_{p+(j-i)}
      // => [i,i+k] are all suboptimal
      // => [0,j) and [0,i+k+1) are suboptimal
      // if i+k+1 < j
      //   j < j+1 and indices in [0,j+1) \ j are suboptimal
      // else
      //   i+k+1 < i+k+2 and indices in [0,i+k+2) \ (i+k+1) are suboptimal
      i += k+1;
      if (i < j)
        i = j++;
      else
        j = i+1;
    }
  }
  // j >= n => [0,n) \ i cannot be the first optimum
  return i;
}
于 2016-05-16T22:30:15.687 に答える