字符串拼接查询

Question

我有一个由x个字符组成的列表，表示为b [1]，b [2]，b [3] ... b [x]。在x之后：

• b [x + 1]是按顺序连接b [1]，b [2] ..... b [x]。同样，

• b [x + 2]是按顺序连接b [2]，b [3] .... b [x]，b [x + 1]。

• 因此，基本上，b [n]将是从右边取出的最后x个b [i]项的连接。

• 给定查询参数p和q，我如何找出b [p]的^q个字符对应于b [1]，b [2]，b [3] ..... b [x]中的哪个字符？

注意：x和b [1]，b [2]，b [3] ..... b [x]对于所有查询都是固定的。

我尝试过暴力搜索，但字符串长度会随着大型x而呈指数级增加。（x ≤ 100）。

---

示例：

• When x=3,

  b[] = a, b, c, a b c, b c abc, c abc bcabc, abc bcabc cabcbcabc, //....  
  //Spaces for clarity, only commas separate array elements
  

• So for a query where p=7, q=5, answer returned would be 3(corresponding to character 'c').

我只是在理解它背后的数学方程式方面有些困难。语言不是问题。

- J.Doe

---

那么对于 x=3，b = a, b, c, a b c, b c abc, c abc bcabc, abc bcabc cabcbcabc 等等？（空格为了清晰起见，仅逗号分隔数组元素） - Mad Physicist

@Mad Physicist写的是正确的。如果有一个查询，其中p = 7，q = 5，则我的答案应该是c或第三个字符。 - J.Doe

提示：元素的长度是高阶斐波那契数列。您需要首先找到哪个（p-i）部分是q所在的，即如果q < HFib(p-x+1, x)或HFib(p-x+1, x) <= q < HFib(p-x+2, x)，依此类推；然后递归。 - lorro

Answer 1

我写下这篇答案是为了自己理解，希望您能耐心看完。

正如您所提到的那样，相比于生成大的p，更容易找出原始x个字符中b[p][q]的来源。为此，我们将使用循环来查找当前b[p][q]的来源，从而减少p直到它在1和x之间，并且q减少到1。

让我们以x=3的例子来看看是否可以得出一个公式：

p  N(p)  b[p]
-  ----  ----
1  1     a
2  1     b
3  1     c
4  3     a b c
5  5     b c abc
6  9     c abc bcabc
7  17    abc bcabc cabcbcabc
8  31    bcabc cabcbcabc abcbcabccabcbcabc
9  57    cabcbcabc abcbcabccabcbcabc bcabccabcbcabcabcbcabccabcbcabc

序列很清晰: N(p) = N(p-1) + N(p-2) + N(p-3)，其中N(p)是b的第p个元素中字符的数量。给定p和x，您可以计算范围[1, p]内所有N。这将帮助您确定b[p][q]来自哪个先前的b元素。

举例说明，假设x=3，p=9，q=45。

1. 上面的图表给出了N(6)=9，N(7)=17和N(8)=31。由于45>9+17，因此您知道b[9][45]来自b[8][45-(9+17)] = b[8][19]。
2. 继续迭代/递归，19>9+5，所以b[8][19] = b[7][19-(9+5)] = b[7][5]。
3. 现在5>N(4)，但5<N(4)+N(5)，因此b[7][5] = b[5][5-3] = b[5][2]。
4. b[5][2] = b[3][2-1] = b[3][1]
5. 由于3 <= x，我们有终止条件，并且b[9][45]是b[3]中的c。

如果有起始值p、q、x和b，那么这样的计算可以很容易地通过递归或迭代来完成。我的方法需要p个数组元素来计算整个序列的N(p)。如果以递归方式工作，可以在数组或堆栈上分配它们。

以下是使用原生Python实现的参考代码（不需要外部导入，尽管numpy可能会有所帮助）：

def so38509640(b, p, q):
    """
    p, q are integers. b is a char sequence of length x.
    list, string, or tuple are all valid choices for b.
    """
    x = len(b)

    # Trivial case
    if p <= x:
        if q != 1:
            raise ValueError('q={} out of bounds for p={}'.format(q, p))
        return p, b[p - 1]

    # Construct list of counts
    N = [1] * p
    for i in range(x, p):
        N[i] = sum(N[i - x:i])
    print('N =', N)

    # Error check
    if q > N[-1]:
        raise ValueError('q={} out of bounds for p={}'.format(q, p))

    print('b[{}][{}]'.format(p, q), end='')

    # Reduce p, q until it is p < x
    while p > x:
        # Find which previous element character q comes from
        offset = 0
        for i in range(p - x - 1, p):
            if i == p - 1:
                raise ValueError('q={} out of bounds for p={}'.format(q, p))
            if offset + N[i] >= q:
                q -= offset
                p = i + 1
                print(' = b[{}][{}]'.format(p, q), end='')
                break
            offset += N[i]
    print()
    return p, b[p - 1]

调用so38509640('abc', 9, 45)会产生以下结果

N = [1, 1, 1, 3, 5, 9, 17, 31, 57]
b[9][45] = b[8][19] = b[7][5] = b[5][2] = b[3][1]
(3, 'c') # <-- Final answer

同样地，在问题的示例中，so38509640('abc', 7, 5) 会产生预期的结果：

N = [1, 1, 1, 3, 5, 9, 17]
b[7][5] = b[5][2] = b[3][1]
(3, 'c') # <-- Final answer

对不起，我想不出更好的函数名: ) 这是足够简单的代码，它应该在Py2和3中同样有效，尽管range函数/类存在差异。

如果有一种非迭代解决这个问题的方法，我会非常好奇。也许有一种使用模运算或其他方法的方式...

- Mad Physicist