无限长字符串

Question

We are given N words, each of length at max 50.All words consist of small case alphabets and digits and then we concatenate all the N words to form a bigger string A.An infinite string S is built by performing infinite steps on A recursively: In ith step, A is concatenated with ′$′ i times followed by reverse of A. Eg: let N be 3 and each word be '1','2' and '3' after concatenating we get A= 123 reverse of a is 321 and on first recursion it will be A=123$321 on second recursion it will be A=123$321$$123$321 And so on… The infinite string thus obtained is S.Now after ith recursion we have to find the character at index say k.Now recursion can be large as pow(10,4) and N which can be large as (pow(10,4)) and length of each word at max is 50 so in worst case scenario our starting string can have a length of 5*(10**5) which is huge so recursion and adding the string won't work.

我想到的是，在第一次递归之后，这个字符串将是一个回文，所以如果我能计算出“$”的pos，我就可以计算任何索引，因为它前后都是回文 看起来像这样：

string='123'
k=len(string)
recursion=100
lis=[]
for i in range(1,recursion+1):
    x=(2**(i-1))
    y=x*(k+1)+(x-i)
    lis.append(y)
print(lis[:10])

输出： [4, 8, 17, 36, 75, 154, 313, 632, 1271, 2550]

现在我有两个问题，首先，我还想在列表中添加相邻“$”的位置，因为在第2次递归之后的位置8处，会有更多的（递归-1）=1个“$”，同样地，对于第3次递归的位置17，在第18和19位还会有（3-1）两个“$”，这将继续下去在递归之前，我必须插入while循环，这将使我的算法给出TLE

^{pr2}$

输出：[4, 8, 9, 17, 18, 19, 36, 37, 38, 39]

找到$的位置背后的想法是，它前后的字符串是一个回文，如果{}的索引是奇数，则前后元素将是字符串的最后一个元素，它前后的元素是偶数，它将是字符串的第一个元素。在

Answer 1

在每组中，S的美元符号数量如下：

1 2 1 3 1 2 1 4 1 2 1 ...

这对应于i在其二进制表示中的尾随零数，加上一：

^{pr2}$

有了这些信息，你可以使用一个循环，从原来的单词大小中减去k然后根据上面的观察结果减去美元的数目。这样你就可以检测出k是指向一美元还是一个单词内。在

一旦k被“标准化”为原始总单词长度限制内的索引，就只剩下一个检查字符是否按正常顺序排列或颠倒。这取决于在上述循环中完成的迭代次数，并对应于i，即它是奇数还是偶数。在

这导致了以下代码：

def getCharAt(words, k):
    size = sum([len(word) for word in words]) # sum up the word sizes
    i = 0

    while k >= size:
        i += 1
        # Determine number of dollars: corresponds to one more than the 
        #   number of trailing zeroes in the binary representation of i
        b = bin(i)
        dollars = len(b) - b.rindex("1")
        k -= size + dollars

    if k < 0:
        return '$'
    if i%2: # if i is odd, then look in reversed order
        k = size - 1 - k
    # Get the character at the k-th index    
    for word in words:
        if k < len(word):
            return word[k]
        k -= len(word)

你可以这样称呼它：

print (getCharAt(['1','2','3'], 13)) # outputs 3

发电机版本

当您需要像这样请求多个字符时，创建一个生成器可能更有趣，只要您继续迭代，它就会一直生成下一个字符：

def getCharacters(words):
    i = 0
    while True:
        i += 1
        if i%2:
            for word in words:
                yield from word
        else:
            for word in reversed(words):
                yield from reversed(word)
        b = bin(i)
        dollars = len(b) - b.rindex("1")
        yield from "$" * dollars

例如，如果您想要从从“a”、“b”和“cd”构建的无限字符串中提取前80个字符，请这样称呼它：

import itertools
print ("".join(itertools.islice(getCharacters(['a', 'b', 'cd']), 80)))

输出：

abcd$dcba$$abcd$dcba$$$abcd$dcba$$abcd$dcba$$$$abcd$dcba$$abcd$dcba$$$abcd$dcba$

Answer 2

这是我对这个问题的解决方案（findIndex的索引从1开始），我基本上是递归地计数，以找到findIndex元素的值。在

def findInd(k,n,findIndex,orientation):
  temp = k # no. of characters covered.
  tempRec = n # no. of dollars to be added
  bool = True # keeps track of if dollar or reverse of string is to be added.
  while temp < findIndex:
    if bool:
      temp += tempRec
      tempRec += 1
      bool = not bool
    else:
      temp += temp - (tempRec - 1)
      bool = not bool
  # print(temp,findIndex)
  if bool:
    if findIndex <= k:
      if orientation: # checks if string must be reversed.
        return A[findIndex - 1]
      else:
        return A[::-1][findIndex - 1] # the string reverses when there is a single dollar so this is necessary
    else:
      if tempRec-1 == 1:
        return findInd(k,1,findIndex - (temp+tempRec-1)/2,False) # we send a false for orientation as we want a reverse in case we encounter a single dollar sign.
      else:
        return findInd(k,1,findIndex - (temp+tempRec-1)/2,True) 
  else:
    return "$"


A = "123"                                         # change to suit your need
findIndex = 24 # the index to be found            # change to suit your need




k = len(A) # length of the string.

print(findInd(k,1,findIndex,True))

我想这也能满足你的时间限制，因为我没有遍历每一个元素。在