2016-03-06 97 views
0

讓我們重複序列,如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即可。

獎勵積分,如果你使它與負指標工作。

就我而言,這是語言不可知的。只需僞代碼或者簡單的數學方程就可以獲得一些關鍵值。

+0

您打算如何處理結果?更具體地說,爲什麼你不能直接在你打算做的任何輸出處理中使用'l'和'r'? –

+0

在你的例子中,你選擇的部分是否也是「cdab」* 3 +「c」會更簡單嗎? – moreON

+0

@OliverCharlesworth對於分區上的操作,這種方法將是O(分區的長度),但這種方法是O(序列的長度),在大多數情況下,這種方法要快得多。我的具體情況是競爭性編程問題。 – user2244484

回答

1

模運算符在這裏是關鍵。來自重複字符串的讀數索引a將在未重複字符串中的索引a % len(s)處讀取。所以例如片s[:end % len(s)]是後綴。

在像Python語言,其中除法舍入向負無窮,而不是朝向零(其中-1 % 3 == 2-1 // 3 == -3代替-1 % 3 == -1-1/3 == 0),對於非負索引的情況下編寫的代碼將自動應用到負折射率的情況。

有兩個棘手的角落案件看在這個問題:

  1. 切片可能的字符串相同的重複內完全下降。在這種情況下,前綴/ rep-count /後綴約定是沒有意義的。不檢查這種情況的代碼會將錯誤的額外字符放入前綴和後綴中,並返回負重複計數。

    slice_cyclic_string('abcd', 1, 3)不應該返回('bcd', -1, 'abc'),它應該回退到原始字符串結果。

  2. 切片可能落在重複邊界上。天真的代碼可能會將重複數據放在前綴或後綴中,而不是重複計數。

    slice_cyclic_string('abcd', 0, 8)應該返回('', 2, ''),不('abcd', 1, '')('', 1, 'abcd')('abcd', 0, 'abcd')

與涉及模,處理棘手的邊界情況最代碼由變速當時unshifting前後模運算後進行了1在隨機的地方。

這裏是Python代碼,你想要做什麼,除了它遵循end指數的蟒蛇慣例是排斥的,指數是從零開始slice_cyclic_string("abcd", 5, 18)返回('bcd', 2, 'ab')

def slice_cyclic_string(repeated_string, start, end): 
    n = len(repeated_string) 

    if start > end: 
     raise ValueError("start > end") 
    if start // n == end // n: 
     # The slice lies entirely within one repetition. 
     return repeated_string[start % n : end % n] 

    prefix = repeated_string[(start-1) % n + 1:] 
    suffix = repeated_string[:end % n] 
    reps = (end - start - len(prefix) - len(suffix)) // n 

    return prefix, reps, suffix 
+0

「與大多數涉及模數的代碼一樣,處理棘手的邊界情況是通過在隨機位置的模運算符之前和之後移位然後取消移位來完成的。」 - 哈哈,這正是我對modulo的體驗,尤其是這個問題。弄清楚定時比賽中+ 1s和-1s的位置並不容易。非常感謝你的解決方案,它完美的工作!現在我只需要記住它。 – user2244484

0

我假設我們開始索引0並且該子數組與星號l+1一致,如您的示例中所示。而不是prefixsufix我想使用sf這是您的前綴的第一個字符的索引和sufix的最後一個字符的重複模式的索引。你的例子中的s=2f=2。我也假設n是重複模式的長度。

s = (l + 1) mod n 
f = r mod n 
repeats = (r-l -(n-s) -(n-f+1))/n 
+0

根據一些快速測試,這不適用於許多邊緣情況。嘗試諸如'abcd | abcdabcdab | cd'或'abcd | abcdabcd | abcd'或者'a | bc | d'。另外,對於提示第一個元素應該是l + 1,我表示歉意,這只是我在例子中的錯誤。 – user2244484