0

長さ n (1 <= n <= 100000) の文字列を考えてみましょう。最小の辞書式回転を決定します。たとえば、文字列「alabala」の回転は次のとおりです。

alabala

labalaa

abalaal

balaala

alaalab

laalaba

aalabal

and the smallest among them is “aalabal”.

この質問は Stack で既に質問されていますが、明確な解決策がないため、再度質問します。今まで、私は次の進歩を遂げました。
1. S を取り、reverse(S)..let P=S+reverse(S) で
連結 2. 上記の文字列 P のサフィックス配列を構築

ここで私の質問は、サフィックス配列の最初の文字列を選択すると、この文字列size> strlen(S)のサイズのプレフィックスがstrlen(S)指定された文字列 S の最小回転になるということです。

私の結論は正しいですか？

4

1 に答える 1

0

いいえ、一般的には間違っています（あなたの言いたいことを正しく理解していれば）。もちろん、回文入力に対しては問題なく機能します。

次の Python インタープリターからの出力を参照してください。ここで、入力文字列には と が含ま'alabala'れ'alabatta'ます。(出力にはいくつかのスペースと改行が追加されています。) 2 番目のセクションでは、S よりも長い最初のサフィックスの前部は許容されません。つまり、S の回転ではありません。動作するアプローチについては、3 番目のセクションを参照してください。

>>> s = 'alabala'; p = s + ''.join(reversed(s))
>>> sorted([p[i:] for i in range(len(p))])
['a', 'aalabala', 'abala', 'abalaalabala', 'ala', 'alaalabala',
 'alabala', 'alabalaalabala', 'bala', 'balaalabala', 'la',
 'laalabala', 'labala', 'labalaalabala']

>>> s = 'alabatta'; p = s + ''.join(reversed(s))
>>> sorted([p[i:] for i in range(len(p))])
['a', 'aattabala', 'abala', 'abattaattabala', 'ala', 'alabattaattabala',
 'attaattabala', 'attabala', 'bala', 'battaattabala', 'la',
 'labattaattabala', 'taattabala', 'tabala', 'ttaattabala', 'ttabala']

>>> s = 'alabatta'; p = s + s
>>> sorted([p[i:] for i in range(len(p))])
['a', 'aalabatta', 'abatta', 'abattaalabatta', 'alabatta', 
 'alabattaalabatta', 'atta', 'attaalabatta', 'batta', 'battaalabatta',
 'labatta', 'labattaalabatta', 'ta', 'taalabatta', 'tta', 'ttaalabatta']
于 2012-11-03T06:31:27.573 に答える