文字列連結クエリ

Question

b[1], b[2], b[3] ... b[x]と表示されている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という用語を連結して、右から左に取ります。 p問合せなどqなどのパラメータを考えると

• 、どのように私は見つけることができますb[1], b[2], b[3]..... b[x]の間でどの文字がb[p]のq番目の文字は、に対応していますか？

注：xとb[1], b[2], b[3]..... b[x]は、すべてのクエリのために固定されています。

私はbrute-forcingを試みましたが、文字列の長さは大きなxに対して指数関数的に増加します（x < = 100）。

---

例：p=7、q=5クエリに対するので

• 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 
  

• 、答えは（文字'c'に相当）3だろう戻りました。

私はちょうどそれの背後にある数学を理解するのが難しいです。言語は問題ありません

Answer 1

私はそれを理解したので、私はこの答えを書いていますので、私にご負担ください。

あなたが述べたように、大きなpためb[p]を生成するよりも、b[p][q]の文字が元x文字の中から来ている場所を見つけるためにはるかに簡単です。これを行うには、ループを使用して現在のb[p][q]がどこから来たのかを調べ、1とxの間になるまでpを減らし、1までqになるまで減らします。

私たちが式を得ることができるかどうか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をブルートフォースで計算できます。これにより、bb[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]です。 3 <= x以来
4. b[5][2] = b[3][2-1] = b[3][1]
5. 、我々は我々の終了条件を持っている、とb[9][45]はb[3]からcです。

このような何かを非常に簡単にxまでp、q、xとbを開始与えられたいずれかの再帰的または反復的に計算することができます。私の方法では配列全体に対してN(p)を計算するにはp配列要素が必要です。これは、再帰的に動作している場合、配列またはスタックに割り当てることができます。 （numpyのはおそらくこれを合理化に役立つだろうが、外付けの輸入、）ここで

はバニラPythonでリファレンス実装です：

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 

申し訳ありませんより良い関数名を思いつくことができません:)これは、関数/クラスrangeの違いにもかかわらず、Py2と3で同じようにうまくいくはずのシンプルなコードです。

この問題の非反復的な解決策があるかどうかは非常に興味があります。おそらく、モジュラ算術または何かを使用してこれを行う方法があります。