字符串连接查询

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] 将是 b[i] 的最后 x 项的串联，取左边从右边开始。

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

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

我尝试了暴力破解，但对于大 x.(x<=100)，字符串长度呈指数增长。

---

示例:

• 当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
  

• 因此对于 p=7，q=5 的查询，返回的答案将是 3(对应于字符 'c').

我只是很难弄清楚它背后的数学原理。语言不是问题

Answer 1

这个答案是我想出来的，所以请多多包涵。

正如您所提到的，找出 b[p][q] 处的字符要容易得多。来自于原创x字符比生成 b[p]对于大 p .为此，我们将使用循环来查找当前 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 , 你可以暴力计算所有 N对于范围 [1, p] .这将使您能够找出 b 的哪个先验元素。 b[p][q]来自。

为了说明，说 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]是c来自 b[3] .

从p 开始，可以很容易地递归或迭代地计算类似这样的东西, q , x和 b最多 x .我的方法需要 p要计算的数组元素 N(p)对于整个序列。如果递归工作，这可以分配在数组或堆栈上。

这里是 vanilla 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 中存在差异。函数/类。

我很好奇这个问题是否有非迭代的解决方案。也许有一种方法可以使用模块化算法或其他东西来做到这一点......