arrays - 计算无限重复字符串的(前缀、重复计数、后缀)切片

Question

让我们无限地重复 abcd 这样的序列，产生以下数组:

abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcd (...)

这就是问题所在:给定两个索引 l 和 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，任何算法都可以很容易地适用于任何这些设置。

如果您使其与负索引一起使用，则可加分。

就我而言，这是与语言无关的。只需伪代码甚至简单的数学方程式即可获得一些临界值就足够了。

Answer 1

模运算符是这里的关键。从重复字符串中读取索引 a 将读取未重复字符串中的索引 a % len(s)。所以例如切片 s[:end % len(s)] 是后缀。

在像 python 这样的语言中，除法向负无穷大而不是向零舍入(其中 -1 % 3 == 2 和 -1//3 == -3 而不是 -1 % 3 == -1 和 -1/3 == 0)，为非负索引情况编写的代码将自动应用于负指标案例。

在这个问题中有两个棘手的极端情况需要注意:

1. 切片可能完全属于字符串的相同重复。在这种情况下，前缀/重复计数/后缀约定没有意义。不检查这种情况的代码会将错误的额外字符放入前缀和后缀中，并返回负的重复计数。

   slice_cyclic_string('abcd', 1, 3) 不应该返回 ('bcd', -1, 'abc')，它应该返回到 a原始字符串结果。

2. 切片可能落在重复边界上。朴素的代码可能会将完整的重复放入前缀或后缀中，而不是放入重复计数中。

   slice_cyclic_string('abcd', 0, 8) 应该返回 ('', 2, '')，而不是 ('abcd', 1, '') 或 ('', 1, 'abcd') 或 ('abcd', 0, 'abcd')

   <

与大多数涉及模的代码一样，处理棘手的边界情况是通过在随机位置的模运算符前后移动 1，然后取消移动 1 来完成的。

这是执行您想要的操作的 python 代码，除了它遵循 end 索引是独占的且索引是从零开始的 python 约定。 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