讓我們重複序列,如abcd
無限,得到以下的數組:計算(前綴,repetition_count,後綴)無限重複的串的切片
abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcd (...)
這就是問題:給定兩個索引升和r(l < r),返回從索引l開始到r結束的子數組。
但由於數組是循環的,因此使用常規數組來表示其分區會浪費內存,而不是原始序列的兩個子數組(前綴和後綴)(此處爲abcd
),而數字表示數分區中序列的完整重複將足以定義分區。
下面是一個例子:
l = 5
r = 18
abcdab|cd.abcdabcd.abc|dabcdabcdabcdabcdabcdabcdabcd (...)
prefix = "cd"
sufix = "abc"
repeats = 2
當然,並不是所有情況下符合這一方案,以便完全像上面的。有時前綴將是空的,有時是後綴,有時不會有整個序列的重複,等等。事實上,有一種特殊情況,當分區完全符合序列的一個重複(abcda|bc|dabcdabcd(...)
)時,它不能用這種方式表示,只應該用一個字符串表示。
而這不是唯一使這個問題變得糟糕的問題。由於它必然包含模塊化算術,因此它隱藏了許多要進行的逐個錯誤。因此,我對包容性或排他性邊界以及0索引和1索引設置了沒有限制。你可以使用任何使數學最簡單的方法。任何算法都可以很容易地適用於任何這些設置,只需在某些參數中加1或減1即可。
獎勵積分,如果你使它與負指標工作。
就我而言,這是語言不可知的。只需僞代碼或者簡單的數學方程就可以獲得一些關鍵值。
您打算如何處理結果?更具體地說,爲什麼你不能直接在你打算做的任何輸出處理中使用'l'和'r'? –
在你的例子中,你選擇的部分是否也是「cdab」* 3 +「c」會更簡單嗎? – moreON
@OliverCharlesworth對於分區上的操作,這種方法將是O(分區的長度),但這種方法是O(序列的長度),在大多數情況下,這種方法要快得多。我的具體情況是競爭性編程問題。 – user2244484